贪心算法_区间选点

题意：
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
输入：
第一行1个整数N（N<=100）
第2~N+1行，每行两个整数a,b（a,b<=100）
输出：
一个整数，代表选点的数目
输入样例：
3
1 3
2 5
4 6
输出样例：
2
解题思路：
首先考虑如果两个区间一个区间包含另外一个，小区间内的点一定在大区间内，但是大区间内的点不一定在小区间内。所以此时，只需要考虑较小的区间。当两个区间不包含但有重叠部分时，选择一个点在b_i更小的区间的最末端，则该点一定包含在两个区间内。我们的对不同区间的排序方式（即贪心准则）是按b_i从小到大i排序所有的区间，当b_i相同时则按照a_i从大到小进行排序。这样排序以后即使有包含的区间，小区间也一定会排在前面。接下来取第一个区间的最后一个点，然后向后查找第一个不包含该点的区间，取该区间的最后一个点，以此类推直到结束。
注意事项：
1、又涉及到排序问题，可以用优先级队列重载小于运算符，也可以重写比较函数然后用sort，我们这里重写比较函数，注意返回值的表达式可以用三目运算符更加简便。
2、题目只要求输出点的个数，所以用一个num记录个数，一个cur_point记录当前右端点即可，不需要额外的动态数组记录具体选择的点的信息（如果题目要求则需要额外的数组来存储）。
总结：
一道经典的贪心算法问题，关键是找对贪心的准则，这里为更小的b_i,或者b_i相同的情况下更大的a_i。显然又涉及到排序问题，不过指标很少用sort或优先级队列都不难解决。
参考代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp (pair<int, int> &a,pair<int, int> &b){
    return a.second<b.second ? true:a.second==b.second&&a.first>b.first;
}
int main(int argc, const char * argv[]) {
    int n;cin>>n;
    vector<pair<int, int> > v;
    int x,y;
    while (n--) {
        cin>>x>>y;
        v.push_back(pair<int, int>(x,y));
    }
    sort(v.begin(), v.end(), cmp);
    int cur_point=v.front().second;
    int num=1;
    for (int i=1; i<v.size(); i++) {
        if(v[i].first>cur_point)
        {
            cur_point=v[i].second;
            num++;
        }
    }
    cout<<num<<endl;
    return 0;
}