会场安排有关问题-贪心算法

会场安排问题--贪心算法

会场安排问题时间限制：3000?ms ?|? 内存限制：65535?KB难度：4

描述

学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。

输入

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)

输出

对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行

样例输入

221 1010 1131 1010 1111 20

样例输出

12

提示

注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始

分析：

这是个贪心算法：

先按照每次活动结束时间进行先后排序，然后选择第一个，然后选择下一个时，开始时间大于上一个结束时间

java代码：

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>{@Overridepublic int compare(Hui o1, Hui o2) {return o1.end.compareTo(o2.end);}}class Hui {public Integer start;public Integer end;}

?C/C++代码：

#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;}        

?