Hdu 2037 今年暑假不AC
今年暑假不AC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 27586 Accepted Submission(s): 14578
Problem Description
“今年暑假不AC？” “是的。” “那你干什么呢？” “看世界杯呀，笨蛋！” “@#$%^&*%...” 确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。 作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
Output
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
Sample Input
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
Sample Output
5
Author
lcy
Source
Recommend
lcy
典型贪心.
最大线段覆盖区间问题.
按照区间结束时间进行升序排序.
因为结束的越早,那么剩下的时间也就越多,可选择的节目就越多.
代码如下：
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6 #define MAX 101
7 struct node
8 {
9 int begin;
10 int end;
11 };
12 struct node p[MAX];
13 int n;
14 bool cmp(struct node x,struct node y)
15 {
16 if(x.end==y.end) return x.begin<y.begin;
17 return x.end<y.end;
18 }
19 void init()
20 {
21 memset(p,0,sizeof(p));
22 }
23 void read()
24 {
25 int i;
26 for(i=0;i<n;i++)
27 scanf("%d %d",&p[i].begin,&p[i].end);
28 sort(p,p+n,cmp);
29 }
30 void cal()
31 {
32 int ans=1;
33 int end=p[0].end;
34 int i;
35 for(i=1;i<n;i++)
36 {
37 if(p[i].begin>=end)
38 {
39 end=p[i].end;
40 ans++;
41 //cout<<p[i].begin<<" "<<p[i].end<<endl;
42 }
43 }
44 printf("%d\n",ans);
45 }
46 void solve()
47 {
48 init();
49 read();
50 cal();
51 }
52
53 int main()
54 {
55 while(scanf("%d",&n)!=EOF&&n)
56 {
57 solve();
58 }
59 return 0;
60 }