活动选择（贪心）

活动选择

　　学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。　　

现在给出n个活动使用礼堂的起始时间begini和结束时间endi(begini < endi)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

【输入】第一行一个整数n(n<=1000)；　

接下来的n行，每行两个整数，第一个begini，第二个是endi(begini< endi <=32767)

【输出】输出最多能安排的活动个数。

【样例输入】

　　3 5

　　1 4

　　12 14

　　8 12

　　0 6

　　8 11

　　6 10

　　5 7

　　3 8

　　5 9

　　2 13

【样例输出】

【思路】：每次都选结束时间最早的，给后面的活动留出给更多的时间，这也许就是贪心吧。。。。眼前光选结束时间最早的为后面留下更多的时间

。。。。。所以按结束时间升序排序，如果活动的开始时间比上一个活动的结束时间早，说明这个活动不能举行

【代码】

 1 //活动选择 
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 using namespace std;
 6 int beginn[1001],endd[1001];
 7 int n,sum=0;
 8 void qsort(int,int);
 9 void slove();
10 int main()
11 {
12     scanf("%d",&n);
13     for(int i=1;i<=n;i++)
14     {
15         scanf("%d%d",&beginn[i],&endd[i]);//输出开始时间和结束时间 
16     }
17     qsort(1,n);//快排 
18     slove();
19     return 0;
20 }
21 void qsort(int x,int y)
22 {
23     int l=x,r=y,m=endd[(x+y)/2];
24     while(l<=r)
25     {
26     while(endd[l]<m)l++;
27     while(endd[r]>m)r--;
28     if(l<=r)
29     {
30         int m=endd[l];endd[l]=endd[r];endd[r]=m;
31         int n=beginn[l];beginn[l]=beginn[r];beginn[r]=n;
32         l++;r--;//经常忘了ORZ 
33     }
34     }
35     if(l<y)qsort(l,y);
36     if(r>x)qsort(x,r);
37 }
38 void slove()
39 {
40     int lastt=-1;
41     for(int i=1;i<=n;i++)
42     {
43         if(beginn[i]>=lastt)//如果开始时间比上一个活动结束时间大说明这个活动能举行 
44         {
45             sum++;//能举行的活动++ 
46             lastt=endd[i];//修改最后一个活动的时间 
47         }
48     }
49     printf("%d",sum);
50 }

活动选择（贪心）

相关推荐