最大不相交区间数量

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

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

输入格式 第一行包含整数N，表示区间数。

接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。

输出格式 输出一个整数，表示可选取区间的最大数量。

数据范围 1≤N≤105, −109≤ai≤bi≤109 输入样例： 3 -1 1 2 4 3 5 输出样例： 2

分析

1. 按照区间的后端点排序
2. 按照右端点找交集，如果有交集pass
3. 选中的区间个数即答案

Code (同905)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
pair<int, int> num[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &num[i].first, &num[i].second);
    }
    sort(num, num + n, [](pair<int, int>& l, pair<int, int>& r) {
        return l.second < r.second;
    });
    int cMax = -2e9, res = 0;
    for (int i = 0; i < n; ++i) {
        if (num[i].first > cMax) {
            cMax = num[i].second;
            res ++;
        }
    }
    cout << res;
}

---

Last update: January 9, 2021