题目描述

难度分:$1500$

输入$n(1 \leq n \leq 2 \times 10^5)$和$n$个闭区间，每个闭区间$[L,R]$都满足$0 \leq L \lt R \leq 10^9$。

能否将这$n$个闭区间分成两组，每组内的区间交集为空？允许一组是空的。

输出YES或NO。

输入样例$1$

3
1 2
2 3
4 5

输出样例$1$

YES

输入样例$2$

4
1 2
2 3
2 3
1 2

输出样例$2$

NO

算法

贪心

先对输入的区间数组$intervals$按照左右端点进行双关键字排序，然后遍历排序后的区间，贪心地进行分组。将第$1$个区间放入第$1$组$one$，遍历后面的区间：

1. 如果$intervals[i]$与$one$的最后一个区间有交集，那它就只能放入第$2$组$two$。但如果$two$不为空，且最后一个区间和$intervals[i]$也有交集，那分组就不可能完成。

2. 如果$intervals[i]$与$one$的最后一个区间没有交集，就直接将$intervals[i]$分入第$1$组。

复杂度

时间复杂度

整个算法的瓶颈在于对$intervals$数组的排序，后续的分组操作其实就是遍历一遍排序后的$intervals$数组，是线性的。因此，算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

分组的时候开辟了$one$和$two$两个数组，用于存放两个组的区间（其实这个空间是可以省掉的，只维护两个组的最右端点）。在最差情况下分组是可以完成的，此时$one$和$two$中的区间数量是$O(n)$的，这也是整个算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int, int> PII;
int n;

bool solve(vector<PII>& intervals) {
    vector<PII> one, two;
    one.push_back(intervals[0]);
    for(int i = 1; i < n; i++) {
        if(one.back().second >= intervals[i].first) {
            if(!two.empty() && two.back().second >= intervals[i].first) {
                return false;
            }else {
                two.push_back(intervals[i]);
            }
        }else {
            one.push_back(intervals[i]);
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    vector<PII> intervals;
    for(int i = 0; i < n; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        intervals.push_back({l, r});
    }
    sort(intervals.begin(), intervals.end());
    if(solve(intervals)) {
        puts("YES");
    }else {
        puts("NO");
    }
    return 0;
}