题目大意:选择不相交区间问题。给定n个区间(a,b),选择尽可能多的区间,是的这些区间两两不相交。
经典贪心问题,将区间按照上界进行排序,选择第一个区间,然后去掉与第一个区间相交的区间,以此类推。
1 #include2 #include 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) const10 {11 return r < x.r;12 }13 };14 Interval interval[MAXN];15 16 int main()17 {18 #ifdef LOCAL19 freopen("in", "r", stdin);20 #endif21 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("\n");39 }40 return 0;41 }