区间与扫描线算法：端点排序和重叠统计

我最开始接触“区间与扫描线算法：端点排序和重叠统计”时，先遇到的是这个问题：我最初处理区间重叠时写了很多 if-else，端点一多就漏情况，后来才学会先把事件放到同一条时间线上。我没有继续硬记结论，而是把过程画出来，再用一两个最小例子亲手跑通。这篇留下的，就是那次重新梳理后真正帮我想明白的东西。

区间题看起来变化很多，比如合并区间、会议室数量、区间覆盖、航班预订、日程冲突。它们共同点是都围绕“左端点、右端点、重叠关系”展开。

区间问题的核心

区间合并与扫描线

图：区间题通常先排序，再根据端点变化维护当前状态

遇到区间题，先问：

区间是否闭合？例如 [l, r] 还是 [l, r)。
是否需要合并重叠区间？
是否需要统计同时存在的区间数量？
是否有大量区间修改或查询？

合并区间

先按左端点排序，然后维护当前合并区间。

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> ans = new ArrayList<>();
    for (int[] cur : intervals) {
        if (ans.isEmpty() || ans.get(ans.size() - 1)[1] < cur[0]) {
            ans.add(cur);
        } else {
            int[] last = ans.get(ans.size() - 1);
            last[1] = Math.max(last[1], cur[1]);
        }
    }
    return ans.toArray(new int[0][]);
}

如果题目认为 [1,3] 和 [3,5] 相交，条件是 lastEnd < curStart；如果认为半开区间不相交，则条件可能要写成 lastEnd <= curStart。

会议室数量：扫描线

统计最多同时进行的会议，可以把每个会议拆成两个事件：开始 +1，结束 -1。

int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] start = new int[n];
    int[] end = new int[n];
    for (int i = 0; i < n; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    Arrays.sort(start);
    Arrays.sort(end);

    int rooms = 0;
    int best = 0;
    int i = 0;
    int j = 0;
    while (i < n) {
        if (start[i] < end[j]) {
            rooms++;
            best = Math.max(best, rooms);
            i++;
        } else {
            rooms--;
            j++;
        }
    }
    return best;
}

这里如果会议结束时间等于另一场开始时间，通常可以复用会议室，所以用 start[i] < end[j]。

差分数组：批量区间修改

如果题目有大量区间加减，逐个元素修改会很慢。差分数组把区间修改变成两个端点操作。

int[] applyRangeAdd(int n, int[][] updates) {
    int[] diff = new int[n + 1];
    for (int[] u : updates) {
        int l = u[0], r = u[1], delta = u[2];
        diff[l] += delta;
        if (r + 1 < diff.length) diff[r + 1] -= delta;
    }
    int[] ans = new int[n];
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        ans[i] = cur;
    }
    return ans;
}

差分适合离线批量更新。如果中途既要修改又要查询，就要考虑线段树或树状数组。

我的分析

区间题最重要的是定义边界。很多 bug 不是算法不会，而是没有明确“端点是否包含”。写代码前，我会先在纸上画两个相邻区间：[1,3] 和 [3,5]，确认它们在当前业务里算不算重叠。

面试题

合并区间为什么要先按左端点排序？
扫描线事件中，开始和结束时间相同应该谁先处理？
差分数组适合什么场景，不适合什么场景？
闭区间和半开区间会如何影响判断条件？
如果区间动态增加和删除，应该考虑什么结构？