HDU1009 (FatMouse' Trade)[贪心] 做题笔记

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1009

贪心，按照每个时间区间的结束时间排序，从小到大贪心找出每一个不重叠的区间即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;

int n;
struct Show {
    int s, t;
    bool operator <(const Show& y) const {
        return t < y.t;
    }
}show[maxn];

int main() {
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &show[i].s, &show[i].t);
        }
        sort(show, show + n);
        int p = 0, cnt = 1;
        for(int i = 1; i < n; i++) {
            if(show[i].s >= show[p].t) {
                cnt++;
                p = i;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}