将区间分成最少组数如何用扫描线求最大重叠数？

简化版

将区间分成最少组数，本质是求同一时刻最多有多少个区间重叠。因为同一组内区间不能相交，最大重叠数就是至少需要的组数。可以用扫描线：左端点加 1，右端点后一个位置减 1，扫最大前缀和。

详细版

如果区间是闭区间 [l,r]，两个区间只要共享端点也算相交，所以事件要写成 l:+1、r+1:-1；或者把开始事件排在结束事件之前。扫描过程中维护当前活跃区间数，最大值就是答案。

也可以把所有端点排序，用优先队列按右端点复用组，但扫描线更直接。时间复杂度通常是 O(n log n)，如果端点范围较小可用差分数组做到 O(n+U)。

完整版教学

一、为什么答案等于最大重叠数

同一组里的区间不能相交。如果某个时刻有 4 个区间同时覆盖它，那么这 4 个区间两两都无法放进同一组，至少需要 4 组。

时间点 x：
区间 A 覆盖 x
区间 B 覆盖 x
区间 C 覆盖 x
区间 D 覆盖 x

另一方面，只要按时间扫描，当前活跃区间数就是当前需要的组数峰值，所以最大重叠数也足够作为答案。

二、闭区间端点为什么要小心

题目通常给的是闭区间 [l,r]。这意味着 [1,3] 和 [3,5] 在点 3 相交，不能放同一组。

区间关系	是否相交
`[1,3]` 与 `[4,5]`	不相交
`[1,3]` 与 `[3,5]`	相交
`[1,3]` 与 `[2,4]`	相交

易错点：闭区间共享端点也算重叠，结束事件不能比同点开始事件先释放。

用 r+1 放结束事件，可以自然表达“覆盖到 r 为止”。

三、扫描线事件怎么设计

对每个区间 [l,r]：

events[l] += 1
events[r + 1] -= 1

按坐标从小到大扫描，当前活跃数 cur += delta，答案取 max(ans, cur)。这和差分数组的思想一致，只是坐标可能很大时用有序 Map 存事件。

[1,3] => 1:+1, 4:-1
[2,5] => 2:+1, 6:-1

当扫到 2 时活跃数为 2，说明两个区间重叠。

四、用数字例子推演

区间：

[5,10], [6,8], [1,5], [2,3], [1,10]

事件：

1:+2
2:+1
4:-1
5:+1
6:+1
9:-1
11:-2

扫描过程中最大活跃数会达到 3，所以最少需要 3 组。注意 [1,5] 在 5 还没结束，[5,10] 在 5 开始，它们在 5 相交。

五、代码模板

int minGroups(int[][] intervals) {
    TreeMap<Integer, Integer> events = new TreeMap<>();
    for (int[] in : intervals) {
        events.merge(in[0], 1, Integer::sum);
        events.merge(in[1] + 1, -1, Integer::sum);
    }
    int cur = 0, ans = 0;
    for (int delta : events.values()) {
        cur += delta;
        ans = Math.max(ans, cur);
    }
    return ans;
}

如果 r 可能等于 Integer.MAX_VALUE，r+1 会溢出，可以改用事件排序并规定同点开始先于结束。

六、和会议室 II 有什么区别

会议室 II 常见语义是半开区间 [start,end)，会议在 end 结束后，另一个会议可以马上在同一时间开始。而本题若是闭区间，共享端点算冲突。

题型	端点语义	同点开始/结束
会议室 II	半开区间	可复用
区间分组闭区间	闭区间	不可复用

面试里要先问清端点语义，否则同样的扫描线会差 1。

七、常见误区与追问

误区：把共享端点当成不相交。 闭区间里 [1,3] 和 [3,5] 是相交的。
误区：答案取区间总数。 只有同时重叠的区间才互相排斥，不是所有区间都要不同组。
误区：r+1 不考虑溢出。 右端点可能很大时要用 long 或事件排序。
追问：为什么最大重叠数就是最少组数？ 最大重叠给出下界，扫描分配可以达到这个下界。
追问：能不能用堆？ 可以，按左端排序并用最小右端堆维护组结束点。
追问：复杂度是多少？ TreeMap 事件排序是 O(n log n)，空间 O(n)。

八、加强记忆

区间分组记成“组数 = 最大同时在线人数”。闭区间就用 l:+1, r+1:-1，扫最大前缀和；半开区间则可以在同一时刻先释放再进入。真正容易错的不是代码，而是端点语义，先判断共享端点算不算冲突。

简化版

详细版