最大不相交区间数量

13 Sep 2024 in Algorithm Pageviews

模板

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

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

输入格式

第一行包含整数 N，表示区间数。

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

输出格式

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

输入样例

3

-1 1

2 4

3 5

输出样例

2

代码实现如下:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int Fun(const vector<vector<int>> &a, int n)
    {
        auto vec = a;
        sort(vec.begin(), vec.begin() + n, [](const vector<int> &a, const vector<int> &b) {
            return make_tuple(a[1]) < make_tuple(b[1]); // 支持多级排序
        });

        int res = 0;
        int end = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (end >= vec[i][0] && end <= vec[i][1]) {
                continue;
            }
            res++;
            end = vec[i][1];
        }
        return res;
    }
};

int main()
{
    constexpr int N = 100010;
    int n = 0;
    cin >> n;
    vector<vector<int>> vec(N, vector<int>(2));
    for (int i = 0; i < n; i++) {
        int l = 0;
        int r = 0;
        cin >> l >> r;
        vec[i][0] = l;
        vec[i][1] = r;
    }
    Solution sol;
    cout << sol.Fun(vec, n);
    return 0;
}