【区间贪心】合理安排电视节目_c语言看尽量多的节目

【题目】

假设你已经知道了所有你喜欢看的电视节目的转播时间表，为了能看尽量多的完整节目，你会合理安排吗？

【输入】

输入数据包含多个测试实例。

第一行只有一个整数 n（n<=100），表示你喜欢看的节目的总数。n=0时表示输入结束，不做处理。

然后是 n 行数据，每行包括两个数据 Tis 和 Tie（1<=i<=n）,分别表示开始和结束时间。

【样例输入】

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<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Program{
    int startTime;
    int endTime;
};
const int MAX=100;
Program arr[MAX];
bool Compare(Program x,Program y)
{
    return x.endTime<y.endTime;
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        for(int i=0;i<n;i++)
            cin>>arr[i].startTime>>arr[i].endTime;
        sort(arr,arr+n,Compare);//按结束时间升序排序
        int currentTime=0;//设置当前时间
        int answer=0;
        for(int i=0;i<n;i++)
        {
            if(currentTime<=arr[i].startTime)
            {
                currentTime=arr[i].endTime;
                answer++;
            }
        }
        cout<<answer;
    }
    return 0;
}