贪心算法的区间问题

选择不相交区间

问题描述：

数轴上有n条线段，选取其中k条线段使得这k条线段两两没有重合部分，问k最大为多少。

输入描述:
第一行为一个正整数n；
在接下来的n行中，每行有2个数ai，bi描述每条线段。

输出描述:
输出一个整数，为k的最大值。

思路：

1. 区间x完全包含y，选y
2. 按照bi从小到大排序，从第一个区间开始选
3. 把所有和上一个区间相交的区间排除在外

思路分析:
首先明确一个问题：假设有两个区间x,y，区间x完全包含y。那么，选x是不划算的，因 为x和y最多只能选一个，选x还不如选y，这样不仅区间数目不会减少，而且给其他区间留出 了更多的位置。接下来，按照bi从小到大的顺序给区间排序。
贪心策略是：一定要选第一个区间。

现在区间已经排序成b1≤b2≤b3…了，考虑a1和a2的大小关系。

情况1：a1>a2，如图所示，

区间2包含区间1。前面已经讨论过，这种情况下一 定不会选择区间2。不仅区间2如此，以后所有区间中只要有一个i满足a1>ai，i都不要选。在今后的讨论中，将不考虑这些区间。
情况2：排除了情况1，一定有a1≤a2≤a3≤…，如图所示。
如果区间2和区间1完全不相交，那么没有影响（因此一定要选区间1），否则区间1和区间2最多只能选一个。如果 不选区间2，区间1的1部分其实是没有任何影响的（它不会挡住任何一个区间），区间1的有效部分其实变成了2部分，它被区间2所包含！由刚才的结论，区间2是不能选的。依此类推,不能因为选任何区间而放弃区间1，因此选择区间1是明智的。
选择了区间1以后，需要把所有和区间1相交的区间排除在外，需要记录上一个被选择的区间编号。这样，在排序后只需要扫描一次即可完成贪心过程，得到正确结果。
解题代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int>PII;//pair的好处是可以直接用sort，不用写小于之类的
bool cmp(PII a, PII b) {
    return a.second < b.second;
}
const int N = 10000100;
PII jl[N];//分别存线段的起点与终点
int n;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> jl[i].first >> jl[i].second;
    }
    sort(jl, jl + n, cmp);

    int ans = 0, k = 0;
    for (int i = 0; i < n; i++) {
        if (jl[i].first >= k) {
            k = jl[i].second;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

思路分析来源：
CSDN分析