今年暑假不AC(简单贪心)

今年暑假不AC

由于题目要求能观看完整节目的最大值，考虑到关于最值的相关算法以及本题的具体要求，因此采用贪心的做法（其他做法未尝试，DP应该也能做出来）。

首先需要对时间段进行排序。

排序的要点是对时间段的右端点排序，这样在选取节目时只需要考虑左端点的选择，由于已经按照右端点排好序，那么下面只需要从第一个节目（时间长度最小的）开始进行遍历就可以了。

不过需要注意的是在进行遍历的时候，假设第 i + 1 个节目可以排在第 i 个节目后面，那么直接排就行了，因为右端点已经是固定好的了，而且在排好后，需要将当前点移到这个第 i + 1 个节目上，然后再进行下面节目的遍历，直到结束。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct Node{
    int s, e;
}node[105];

bool cmp(Node a, Node b){
    return a.e <= b.e;
}
int main(){
    int n;
    while(cin >> n){
        if(n == 0)
            break;
        for(int i = 1; i <= n; i ++)
            cin >> node[i].s >> node[i].e;
        sort(node + 1, node + n + 1, cmp);
        int cnt = 0;
        //按照右端排序后就只需要考虑左端，
        for(int i = 1, j = 2; j <= n; j ++){
            if(node[j].s >= node[i].e){
                cnt ++;
                i = j;
            }
        }
        cout << cnt + 1 << endl;
    }

    return 0;
}