题目描述

给定N个闭区间[ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

样例

3
-1 1
2 4
3 5

2

贪心

以右端点从小到大排序后从左至右扫一遍所有线段，扫描时维护一个 lastr 表示此区间的前一个区间的右端点坐标。若此区间的左端点坐标 > lastr，表示该区间与上一个区间不相交，计入答案.

时间复杂度

排序为 $O(n log_2 n)$，扫描一遍为 $O(n)$，总计 $O(n log_2 n)$。

C++ 代码

很好写，一遍 debug 都没有就通过了.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

struct Segment {
    int l, r;
    inline friend bool operator < (const Segment &a, const Segment &b) {
        return a.r < b.r;
    }
} a[N];

int n;
signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + n + 1);

    int answer = 0, lastr = a[1].l - 1;

    for (int i = 1; i <= n; ++i) {
        if (a[i].l > lastr) ++answer, lastr = a[i].r;
    }

    printf("%d\n", answer);
    return 0;
}