活动安排问题
Time Limit:1000MS Memory Limit:65536KTotal Submit:139 Accepted:3
Description
假设要在一会场里安排一批活动，并希望尽可能多的安排活动。设计一个有效的算法计算当所安排的活动最多时，会场的使用时间。会场的使用时间是指活动占用会场的时间，例如一活动在1到23分占用会场，那么会场的使用时间就是23分。 编程任务： 对于给定的k个待安排的活动，编程计算安排的活动最多时会场使用时间。
Input
输入数据是由多组测试数据组成。每组测试数据输入的第一行有1 个正整数k(k≤8500)，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
Output
对应每组输入，输出的每行是计算出的会场使用时间。
Sample Input
5 1 23 12 28 25 35 27 80 36 50
Sample Output
49
Source
wangzhiqun
[Submit] [Go Back] [Status] [Discuss]
// 13222 wupanlei 1072 Accepted 952K 399MS G++ 0.8K 2009-06-24 08:20:57 #include < iostream > #include < algorithm > #define MAX 9000 using namespace std;typedef struct node{ int s; int e;}Data; class Party{ private : Data data[MAX]; int summ; int n; public : Party(); void Set( int nn); // friend bool comp(int a,int b); int CalSum();}; bool comp(node a,node b){ return a.e < b.e;}Party::Party(){ summ = 0 ;} void Party::Set( int nn){ n = nn; int i; for (i = 0 ;i < n;i ++ ) { cin >> data[i].s >> data[i].e; }} int Party::CalSum(){ int j = 0 ,i; sort(data + 0 ,data + n,comp); summ = data[ 0 ].e - data[ 0 ].s + 1 ; for (i = 1 ;i < n;i ++ ) { if (data[i].s >= data[j].e) { summ += data[i].e - data[i].s + 1 ; j = i; } } return summ;} int main(){ int nn; while (cin >> nn) { Party p; p.Set(nn); cout << p.CalSum() << endl; } return 0 ;}
转载于:https://www.cnblogs.com/forever4444/archive/2009/06/24/1509882.html
