记录一道有意义的算法题——统计不重叠的区间个数

题面

参考代码

▼
java
复制代码
    /**
     * 孤立区间 —— 统计不重叠区间的个数
     * 逻辑
     * @param intervals int[][] — 闭区间集合，元素为 {start, end}，表示 [start, end] 这个闭区间。
     * @return int
     */
    public int getIsolationInterval(int[][] intervals) {
        // write code here
        // 先排序吧，排序规则：先按起点升序，若相同再按终点升序
        Arrays.parallelSort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return Integer.compare(o1[0], o2[0]);
            }
            return Integer.compare(o1[1], o2[1]);
        });
        // 对每个区间 i：
        // 1. 如果 i > 0，则检查左边最大 end < 当前 start
        // 2. 如果 i < n - 1，则检查当前 end < 右边最小 start
        // 3. 两个方向都满足，则当前区间是孤立区间
        int[] prefixMaxEnd = new int[intervals.length];
        prefixMaxEnd[0] = intervals[0][1];
        for (int i = 1; i < prefixMaxEnd.length; i++) {
            prefixMaxEnd[i] = Math.max(prefixMaxEnd[i - 1], intervals[i][1]);
        }
        
        int[] suffixMinStart = new int[intervals.length];
        suffixMinStart[intervals.length - 1] = intervals[intervals.length - 1][0];
        for (int i = suffixMinStart.length - 2; i >= 0; i--) {
            suffixMinStart[i] = Math.min(suffixMinStart[i + 1], intervals[i][0]);
        }
        
        int result = 0;
        for (int i = 0; i < intervals.length; i++) {
            boolean q1 = true, q2 = true;
            if (i > 0) {
                q1 = prefixMaxEnd[i - 1] < intervals[i][0];
            }
            if (i < intervals.length - 1) {
                q2 = suffixMinStart[i + 1] > intervals[i][1];
            }
            if (q1 && q2) {
                result++;
            }
        }
        return result;
    }

关键点

这题的关键点可以总结成 5 个：

1. 先排序 按 start 升序排序。这样当前区间左边的区间都在 [0, i-1]，右边都在 [i+1, n-1]。

2. 孤立区间要同时满足两个条件 对当前 [start, end]：

   • 左边没有重叠：左边最大 end < start
   • 右边没有重叠：右边最小 start > end

3. 不要只比较相邻区间 [2,3] 和 [4,5] 不重叠，不代表 [4,5] 没有和更左边的 [1,10] 重叠。

4. 用前缀/后缀预处理避免 O(n²)

   • prefixMaxEnd[i]：[0...i] 中最大的 end
   • suffixMinStart[i]：[i...n-1] 中最小的 start

   这样每个区间判断左右情况都是 O(1)。

最终复杂度：

▼
text
复制代码
排序：O(n log n)
预处理：O(n)
统计：O(n)

总复杂度：O(n log n)
空间复杂度：O(n)

你这次真正掌握的其实不只是这道题，而是一个很常用的套路：排序 + 前缀/后缀预处理，把反复查询转换成 O(1) 查询。