ZOJ 1076 Gene Assembly

　　题目大意：选择不相交区间问题。给定n个区间（a,b），选择尽可能多的区间，是的这些区间两两不相交。

　　经典贪心问题，将区间按照上界进行排序，选择第一个区间，然后去掉与第一个区间相交的区间，以此类推。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MAXN 1000+10
 5 
 6 struct Interval
 7 {
 8     int l, r, num;
 9     bool operator < (const Interval& x) const
10     {
11         return r < x.r;
12     }
13 };
14 Interval interval[MAXN];
15 
16 int main()
17 {
18 #ifdef LOCAL
19     freopen("in", "r", stdin);
20 #endif
21     int n;
22     while (scanf("%d", &n) != EOF && n)
23     {
24         for (int i = 0; i < n; i++)
25         {
26             scanf("%d%d", &interval[i].l, &interval[i].r);
27             interval[i].num = i + 1;
28         }
29         sort(interval, interval+n);
30         int start = interval[0].r;
31         printf("%d", interval[0].num);
32         for (int i = 0; i < n; i++)
33             if (interval[i].l > start)
34             {
35                 start = interval[i].r;
36                 printf(" %d", interval[i].num);
37             }
38         printf("
");
39     }
40     return 0;
41 }

View Code