贪心区间组合问题
具体题目：问题陈述
随着大量基因组DNA序列数据的提供，发现这些序列中的基因（负责蛋白质合成的基因组DNA部分）变得越来越重要。已知对于真核生物（与原核生物相反），这个过程更加复杂，因为存在干扰基因组序列中基因编码区域的垃圾DNA。也就是说，一个基因由几个编码区域的片段（称为外显子）组成。已知外显子的顺序在蛋白质合成过程中保持不变，但外显子的数量和长度可以是任意的。
大多数基因发现算法分为两步：首先搜索可能的外显子；然后尝试组装一个最大可能的基因，通过找到具有最大可能数量的外显子的链。这个链必须遵守外显子在基因组序列中出现的顺序。如果外显子i的结束在外显子j的开始之前，则我们说外显子i在外显子j之前出现。
这个问题的目标是，给定一组可能的外显子，找到可以组装成基因的具有最大可能数量的外显子的链。
输入格式
给出多个输入实例。每个实例以可能外显子数量0 < n < 1000开头。然后，接下来的n行中，每行包含一对整数，表示外显子在基因组序列中的起始和结束位置。您可以假设基因组序列最多有50000个碱基。输入以单个0结尾。
输出格式
对于每个输入实例，您的程序应该在一行中打印具有最大可能外显子数量的链，枚举链中的外显子。如果有多个具有相同外显子数量的链，则您的程序可以打印其中任何一个。

题意：找到最大个数的不重合区间的组合

思路：对区间的左端点排序后，从第一个区间开始向后找，如果符合题意就加上，否则不加，更新组合右端点，这样就是最优解

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
struct Range{
    int id;
    int l, r;
    bool operator < (const Range &s) const{
        return l < s.l;
    }
} range[N];
int n;
int main(){
    while(cin >> n){
        if(n == 0) break;
        for (int i = 1; i <= n; i++){
            cin >> range[i].l >> range[i].r;
            range[i].id = i;
        }
        sort(range + 1, range + n + 1);
        int last = 0;
        for (int i = 1; i <= n; i++){
            if(range[i].l > last){
                printf("%d ", range[i].id);
                last = range[i].r;
            }
        }
        puts("");
    }
    return 0;
}