预计阅读时间：5 分钟

区间

区间题看着花样多，拆开来常常只剩一件事：把每个区间拆成「开始」和「结束」两个事件，按时间扫一遍。本合集收录区间类题目。

资源数 = 最大重叠数

leetcode 253

给一组会议 [start, end]，求最少需要几间会议室。

我的第一版：排序 + 堆，模拟分配。 按开始时间排序，堆里放每间会议室什么时候空出来。新会议到来时看最早空出来的那间：能用就复用，不能用就新开。11 分钟 AC：

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        hp = []
        intervals.sort()
        for s, e in intervals:
            if hp and s >= hp[0]:
                heapq.heappop(hp)
            heapq.heappush(hp, e)
        return len(hp)

（原版两个分支都 push，ans 和 len(hp) 始终相等，这里压成了三行。）

关键观察：答案就是同一时刻最多有几个会议在开。

• 至少要这么多：某一刻有 k 个会议同时进行，它们各占一间，至少 k 间。
• 这么多一定够：按开始时间处理，有空房就复用，没有才新开。新开那一刻所有已开的房都被占着，所以开出来的间数就是当时的重叠数，不会超过最大重叠数。

想通这一点，题目就从「分配房间」变成了「数重叠」：会议室彼此没有区别，谁进哪间根本不重要。堆其实在回答一个用不着问的问题。

扫描线：只数数，不分配。 每个会议拆成 +1（开始）和 -1（结束）两个事件，按时间扫一遍，记录进行中的会议数最多到过多少。开始时间和结束时间分别排序，就是两条已排好序的事件流，用双指针按时间合并：

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(s for s, _ in intervals)
        ends = sorted(e for _, e in intervals)
        rooms = j = 0
        for s in starts:
            if s < ends[j]:    # 还没有会议结束 -> 新开一间
                rooms += 1
            else:              # 最早结束的已经走了 -> 复用
                j += 1
        return rooms

开始和结束拆开各自排序后，就对不上原来是哪个会议了，为什么还对？因为我们只关心「此刻有没有人刚走」，不关心是谁走的。

差分写法。 坐标范围小的话，直接开数组 d[s] += 1, d[e] -= 1，再求前缀和，就得到每个时刻有几个会议在开。坐标到 1e9 开不了数组，就只保留出现过的坐标，排序后再求前缀和——这就是扫描线：扫描线就是稀疏版的差分。

d = Counter()
for s, e in intervals:
    d[s] += 1
    d[e] -= 1
return max(accumulate(d[t] for t in sorted(d)), default=0)

端点相接是唯一的坑。 [1,5] 接 [5,8] 可以共用一间，同一坐标要先算结束、再算开始：双指针里写 s < ends[j]，不能写 <=；差分里同一坐标的 +1 和 -1 落在同一个桶里，先抵消掉了。随机对拍 5000 组，三种写法和暴力全部一致；把 < 改成 <= 后错了 730 组。

复杂度：三种写法都是时间 $O(n \log n)$、空间 $O(n)$，瓶颈在排序。

可以迁移的问法。 只要题目问「最少需要多少资源，才能同时容纳所有区间」（会议室、站台、车辆容量、CPU），答案就是最大重叠数，用扫描线或差分来数，不必真的分配：

本文由 aboom 原创，转载请注明出处。