区间贪心算法

给出N个开区间(x,y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集。

• 区间被包含，选择区间长度短的
• 区间有交叉，选择左端点最大的区间，如果左端点相同，则选择右端点最小的

输入：

4
1 3
2 4
3 5
6 7

输出：

3

//
// Created by heolis on 19-5-16.
//

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

struct Inteval {
    int x, y;   // 开区间端点
} I[maxn];

bool cmp(Inteval a, Inteval b) {
    if (a.x != b.x)
        return a.x > b.x;
    else
        return a.y < b.y;
}

int main() {
    int n;
    while (scanf("%d", &n), n != 0) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &I[i].x, &I[i].y);
        }
        sort(I, I + n, cmp);    // 区间排序
        // ans 记录不相交区间个数，lastX记录上一个被选中区间的左端点
        int ans = 1, lastX = I[0].x;
        for (int i = 1; i < n; i++) {
            if (I[i].y <= lastX) { // 如果这个区间端点在lastX左边
                lastX = I[i].x; // 以I[i]作为新选中区间
                ans++;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}