会场安排问题
时间限制:3000 ms | 内存限制:65535 KB
难度:4
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi<=Ei)
每组的输出占一行
2 2 1 10 10 11 3 1 10 10 11 11 20
1 2
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scannner = new Scanner(System.in); int m, n; m = scannner.nextInt(); for (int i = 0; i < m; i++) { n = scannner.nextInt(); List<Hui> list = new ArrayList<Hui>(); for (int j = 0; j < n; j++) { Hui hui = new Hui(); hui.start = scannner.nextInt(); hui.end = scannner.nextInt(); list.add(hui); } Collections.sort(list, new sort()); int num = 1; int end = list.get(0).end; for(int k=1;k<n;k++){ if(list.get(k).start>end){ end = list.get(k).end; num++; } } System.out.println(num); } } } class sort implements Comparator<Hui>{ @Override public int compare(Hui o1, Hui o2) { return o1.end.compareTo(o2.end); } } class Hui { public Integer start; public Integer end; }
#include<iostream> #include<fstream> #include<vector> #include<algorithm> using namespace std; struct activ { int begin; int end; }; bool cmp(activ a,activ b) { return a.end<b.end; } int main() { ifstream cin("input.txt"); int n; cin>>n; while (n--) { int i,m; cin>>m; vector<activ> vec; for(i=0;i<m;i++) { activ a; cin>>a.begin>>a.end; vec.push_back(a); } sort(vec.begin(),vec.end(),cmp); int count=vec.size(); int k=0; for (i=1;i<vec.size();i++) { if(vec[i].begin <= vec[k].end) count--; else k=i; } cout<<count; } return 0; }
相关推荐
用贪心算法解决会场按排问题,用netbeans6.8做的。已经编译通过没任何错误,JAVA 源文件。
贪心算法之会场安排问题,直接可运行,python文件
会议安排问题(贪心算法) VC下调试OK
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于给定...
贪心算法 会场安排问题 算法设计分析.doc
贪心算法 会场安排问题.doc
贪心算法会场安排问题算法设计分析
贪心算法(会场安排)源代码.txt
会场安排问题 超实用简洁 算法设计与分析 贪心法解决
1.贪心算法解决问题的策略是只考虑眼前情况。2.由题目可知会议需要按时举行,并且会场使用个数最少,即尽可能的提高会场的利用率。3.策略为:将会议按开始时间顺序进行排序,同时记录所使用的会场的结束时间,如果...
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 用C++语言实现
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
贪心算法,会场安排,可直接运行,本人已调试成功
关于会场问题的简单贪心算法 C++算法 正确性已经验证过
假设我们要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设一个有效地贪心算法来进行安排(着色问题)
会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
在会场资源足够多的条件下,对n个活动进行安排,以达到最少会场使用量。文中对这个问题进行了算法分析,并给出了C语言实现。