算法刷题系列（四十六）：扫描线——按事件顺序维护动态状态

算法刷题系列（四十六）：扫描线——按事件顺序维护动态状态

扫描线把二维或区间问题转化为按一个坐标排序的一维事件序列。沿坐标轴从左到右移动时，只处理状态发生变化的位置，而不是在每个点重复检查所有对象。

以会议室安排为例：给定若干时间区间，求同时进行的会议最多有多少个。把每段会议 [start,end) 转成两个事件：开始时活跃数量加一，结束时减一。按时间排序并维护当前活跃数，经过所有事件的最大值就是答案。

为什么半开区间和事件顺序重要

区间 [2,5) 表示时间 2 开始、时间 5 不再占用资源。若一场会议在 5 结束、另一场在 5 开始，它们不重叠，可以共用同一房间。因此同一时间点必须先处理结束事件，再处理开始事件。

扫描过程的不变量是：处理完当前时刻所有事件后，active 等于该时刻之后（下一个不同事件时间之前）正在进行的区间数。结束事件减一，开始事件加一；active 的最大值就是最大并发数量。

若需要明确重叠长度或面积，可以在处理同一坐标的事件前先用“当前状态 × 坐标差”累计贡献，再统一更新该坐标的事件。事件顺序应由区间端点采用闭区间还是半开区间决定。

Java 实现

import java.util.Arrays;

public class Main {
    static class Event {
        int time;
        int delta; // -1 结束，+1 开始
        Event(int time, int delta) { this.time = time; this.delta = delta; }
    }

    static int maximumConcurrent(int[][] intervals) {
        if (intervals == null) throw new IllegalArgumentException("intervals must not be null");
        Event[] events = new Event[intervals.length * 2];
        int p = 0;
        for (int[] interval : intervals) {
            if (interval == null || interval.length != 2 || interval[0] > interval[1])
                throw new IllegalArgumentException("expected start <= end");
            if (interval[0] == interval[1]) continue; // [t,t) 是空区间
            events[p++] = new Event(interval[0], 1);
            events[p++] = new Event(interval[1], -1);
        }
        events = Arrays.copyOf(events, p);
        Arrays.sort(events, (a, b) -> {
            int byTime = Integer.compare(a.time, b.time);
            return byTime != 0 ? byTime : Integer.compare(a.delta, b.delta);
        });
        int active = 0, best = 0;
        for (Event event : events) {
            active += event.delta; // -1 排在 +1 前面，相同端点可无缝衔接
            best = Math.max(best, active);
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 4}, {2, 5}, {5, 7}, {3, 6}};
        System.out.println(maximumConcurrent(intervals)); // 3
        System.out.println(maximumConcurrent(new int[][]{{4, 4}})); // 0
    }
}

零长度区间 [t,t) 不占用任何时间，构造事件时应忽略它。若把它的开始、结束都加入事件，按“结束先于开始”处理会在该时刻暂时减少活跃数，干扰其他同刻事件的统计。本文 Java 与 Python 实现都过滤空区间。

Python 实现

def maximum_concurrent(intervals: list[tuple[int, int]]) -> int:
    if intervals is None:
        raise ValueError("intervals must not be None")
    events: list[tuple[int, int]] = []
    for start, end in intervals:
        if start > end:
            raise ValueError("expected start <= end")
        if start == end:  # 空半开区间不占用资源
            continue
        events.append((start, 1))
        events.append((end, -1))
    events.sort()  # 同时刻 -1 结束事件先于 +1 开始事件
    active = best = 0
    for _, delta in events:
        active += delta
        best = max(best, active)
    return best

assert maximum_concurrent([(1, 4), (2, 5), (5, 7), (3, 6)]) == 3
assert maximum_concurrent([(1, 3), (3, 8)]) == 1
assert maximum_concurrent([(4, 4)]) == 0
assert maximum_concurrent([]) == 0

复杂度、边界与常见错误

若有 n 个区间，事件数为 2n，排序时间 O(n log n)，扫描 O(n)，空间 O(n)。空输入返回 0。若区间定义为闭区间 [start,end]，在端点相同处仍算重叠，开始事件应先于结束事件；不能直接沿用半开区间的同点排序。

常见错误包括忘记同坐标事件的优先级、将结束时间误视为仍占用、只看开始事件而漏掉状态减少、把最大并发误以为一定要显式分配房间，以及允许零长度区间却不定义其语义。若题目要求输出每场会议分配到的具体房间，需要再用最小堆维护房间释放时间；只求最大并发时，扫描事件已经足够。

小结

扫描线的本质是“排序事件 + 维护不变量”。区间端点的开闭语义决定同一坐标的处理顺序；把这条规则写清楚，动态状态的更新和答案统计就容易验证。