统计不重叠区间数量

题目描述

给定一个二维数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]（starti 和 endi 都是整数）。这些区间之间可能存在重叠，请统计跟其他任何区间都不重叠的区间数量。

区间重叠判定： 两个区间 [a, b] 和 [c, d] 重叠，当且仅当一个区间的起点 ≤ 另一个区间的终点且另一个区间的起点 ≤ 该区间的终点。

数据范围：

• 1 ≤ intervals.length ≤ 10000
• intervals[i].length == 2
• 0 ≤ starti ≤ endi ≤ 10000

示例

示例1：

输入：[[8,10],[1,4],[2,6],[15,18]]
输出：2

说明：区间 [8,10] 和 [15,18] 跟其他区间都不重合。

示例2：

输入：[[2,4],[4,6]]
输出：0

说明：[2,4] 和 [4,6] 这 2 个区间重叠（在端点 4 处相接也算重叠），不存在跟其他区间都不重叠的区间，故返回 0。

解题思路

核心思路：排序 + 相邻检查

1. 按起点排序：将所有区间按 start 升序排列。
2. 检查每个区间：对于排序后的第 i 个区间，只需检查它是否与相邻区间重叠：
   • 与左边的区间 i-1 是否重叠：list[i-1][1] >= list[i][0]
   • 与右边的区间 i+1 是否重叠：list[i][1] >= list[i+1][0]
3. 为什么只需检查相邻？ 排序后，如果一个区间与不相邻的区间重叠，那么它必然也会与它们中间的某个相邻区间重叠。因此只需要检查直接相邻的区间即可。

代码实现

function getCount(list) {
    // 按起点排序
    list.sort((a, b) => a[0] - b[0]);
    let c = 0;
    for (let i = 0; i < list.length; i++) {
        let overlap = false;
        // 检查是否与右边区间重叠
        if (i + 1 < list.length && list[i][1] >= list[i + 1][0]) {
            overlap = true;
        }
        // 检查是否与左边区间重叠
        if (i - 1 >= 0 && list[i - 1][1] >= list[i][0]) {
            overlap = true;
        }
        if (!overlap) c++;
    }
    return c;
}

复杂度分析

• 时间复杂度： O(n log n)，排序占主导，遍历检查为 O(n)。
• 空间复杂度： O(1)，原地排序，只使用常数额外空间。

[[8,10],[1,4],[2,6],[15,18]]

2