问题 A: 看电视

题目描述

暑假到了，小明终于可以开心的看电视了。但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目。 现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？

输入

输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。 接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。 当n=0时，输入结束。

输出

对于每组输入，输出能完整看到的电视节目的个数。

样例输入

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

样例输出

5

思路：

贪心算法，对每个节目的结束时间进行递增排序，然后再统计即可，

#include<bits/stdc++.h> using namespace std; struct show { int left; int right; }; bool cmp(show a , show b) { return a.right < b.right; } int main() { int n; while(cin >> n && n!=0) { struct show tv[n]; for(int i=0;i<n;i++) { cin >> tv[i].left >> tv[i].right; } sort(tv, tv+n, cmp); int index = 1; // 统计可以看多少个完整的电视节目 int last = tv[0].right; for(int i=1;i<n;i++) { if(last <= tv[i].left) { last = tv[i].right; index++; } } cout << index << endl; } return 0; }