所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

一、为什么单独立一篇

区间题在之前的笔记里散落在五篇，而且分类依据不统一——有的按数据形态分，有的按用了什么工具分，有的按方法分：

一个连贯的家族被切成五块，结果是：遇到新的区间题，不知道该往哪个抽屉里找。

本篇按「这道题在问什么」重新组织。原文都保留在各自篇里，本篇给出统一的判据和心智模型，并补上之前缺的几道。

二、先问一句：这道题在问什么

几乎所有区间题都落在下面六类之一。先认出问的是哪一类，方法就定了。

最容易混的是第二类和第三类，它们问的是相反的量：

• 第二类求最大不重叠数——能挑出多少个互不相交的（挑出来的越多越好）
• 第三类求最大同时重叠数——某一点上最多压了几层（这是个客观量，没有可挑的）

三、前置动作：排序，以及按哪一端排

区间题几乎都要先排序，但按左端还是按右端，取决于转移需要什么信息：

• 按左端排：处理「合并 / 插入」时用。因为合并的判断是「下一个的起点是否落在当前已合并段的终点之前」，需要起点有序。
• 按右端排：处理「最多留几个不重叠」时用。因为贪心的依据是「结束得越早，给后面留的空间越大」。
• 按右端排：1235 这种带权 DP 也用。因为转移要查询「在我开始之前已经全部结束的那些区间」，这是关于结束时间的查询，只有按结束时间排序，二分才成立。
• 不排序，改成拆事件：第三类（求最大重叠数）根本不需要保持区间完整，把每个区间拆成「起点 +1、终点 −1」两个事件，按时间排序即可。

四、等号归属：端点相接算不算重叠

这是整个区间家族最高频的坑，几乎每道题都要单独确认一次，而且各题约定不同：

435 和 452 只差一个等号，结论却相反。所以做题时第一件事是拿 [1,2] 和 [2,3] 去问一遍题目，别靠记忆。

在扫描线写法里，这个等号表现为同一时刻事件的排序优先级：相接算不冲突，就要让 −1（结束）排在 +1（开始）前面。

具体题目

类型一：合并与插入

56. Merge Intervals / 57. Insert Interval

按左端排序后三段式扫描：完全在左边的原样搬运、有交集的一整段吞掉并边吞边撑大、完全在右边的原样搬运。

关键是三段的循环条件都写成 i < n && ...，每一段都允许执行 0 次，于是「目标在最前 / 在最后 / 夹在中间 / 数组为空」四种边界全部由「循环跑 0 次」自动覆盖，不需要单独讨论。

详细推导见《总结（一）》57 题。

类型二：最多留几个互不重叠 —— 真贪心

435. Non-overlapping Intervals / 452. Minimum Number of Arrows

按结束时间升序排序，然后能留就留。正确性靠交换论证：一定存在一个最优解包含「结束最早」的那个区间，因为把最优解里结束最早的那个换成全局结束最早的那个，不会破坏互不重叠，个数也不变。

直觉就是一句话：结束得越早，给后面留的空间越大。

两题只差一个等号（相接算不算重叠），详见《总结（十五）》。

类型三：某一刻最多叠了几个 —— 扫描线 / 差分计数

252. Meeting Rooms

题意：给出会议时间区间数组，判断一个人能否参加全部会议。

解：按开始时间排序，然后看相邻两个是否冲突即可。

bool canAttendMeetings(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    for (int i = 1; i < intervals.size(); i++)
        if (intervals[i][0] < intervals[i-1][1]) return false;   // 严格小于才算冲突
    return true;
}

用严格的 <，意味着端点相接不算冲突（上一个会 10 点结束、下一个 10 点开始，能参加）。

本质上它是 253 的判定版：能参加全部会议，等价于「最大同时重叠数 <= 1」。

253. Meeting Rooms II

题意：给出会议时间区间数组，求最少需要几间会议室。

解：先要看清一件事——

答案 = 最大同时重叠区间数

两个方向一夹就能证明：下界是某一刻有 k 个会同时进行，那一刻就必须有 k 间房；上界是 k 间房一定够用（按时间扫描分配即可构造出来）。下界等于上界，所以答案就是它。

这不是贪心题。虽然常被归到贪心（”复用最早结束的房间”听起来很贪心），但换成复用任意一个空闲房间，答案完全一样——不存在会影响答案的选择，所以不存在贪心选择，也就不需要交换论证。堆只是一个判断「有没有房间空着」的高效工具。

对比 435：选 [1,100] 还是选 [2,3]，答案真的不同（1 个 vs 2 个），那才是真贪心。

写法一：堆里装「当前正在开的会」（建议先想这个）

这是最贴近题目定义的模型：堆里存正在进行中的会议的结束时间，堆的大小就是当前重叠数，答案是这个大小在整个过程中的峰值。

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());             // 按开始时间
    priority_queue<int, vector<int>, greater<int>> pq;     // 堆里存结束时间
    int res = 0;
    for (auto& it : intervals) {
        while (!pq.empty() && pq.top() <= it[0]) pq.pop(); // ① 先清掉已结束的
        pq.push(it[1]);                                    // ② 再把自己加进来
        res = max(res, (int)pq.size());                    // ③ 再记录峰值
    }
    return res;
}

三步顺序不能乱：若先压入再清理，[[1,2],[3,4]] 会先得到 {2,4}、size=2，答案算成 2（正确是 1）。必须先把过期的清掉，再数当前重叠数。

复杂度仍是 O(NlogN)。内层那个 while 单次可能弹很多个，但每个会议一生只进堆一次、出堆至多一次，所以整个过程弹堆总次数不超过 N，摊还下来每轮 O(1) 次。这个「单次可能很贵，但总量有上界」的论证，和滑动窗口里「left/right 只增不减，总计 O(2N)」、单调栈里「每个元素进栈一次出栈一次」是同一个摊还论证的第三次出现。

这个写法的好处是语义一路透明：堆 = 当前在开的会，堆大小 = 当前重叠数，答案 = 峰值，每一步都直接对应「最大同时重叠数」这个定义，不需要任何额外的转换。

写法二：堆里装「已经开出的房间」（代码更短，但语义拐了个弯）

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());            // 按开始时间
    priority_queue<int, vector<int>, greater<int>> pq;    // 堆里存结束时间
    for (auto& it : intervals) {
        if (!pq.empty() && it[0] >= pq.top()) pq.pop();   // 相接可复用，用 >=
        pq.push(it[1]);
    }
    return pq.size();
}

比写法一少了一个 while、少了一个 res 变量，但代价是语义不再直白。它有五个环节必须都想通，少一个就会觉得”缺了点什么”。

（0）堆里存的是什么——这是最容易第一眼没看见的一点

堆里每个元素 = 一间正在被占用的房间，值是它什么时候空出来。所以：

堆的大小 = 到目前为止一共开了几间房

return pq.size() 不是”剩下几个会没排”，是”开了几间房”。这句话是整个解法的语义基础，没建立起来的话，后面每一步都会觉得别扭。

（1）为什么只需要检查堆顶一个

堆顶是最早结束的那间。如果连它都还没结束（start < 堆顶），那其余房间结束得更晚，必然也都还占着。所以不必遍历所有房间。这正是堆把 O(N^2) 降到 O(NlogN) 的原因。

（2）为什么每次最多只弹一个

假设此刻有三间房都空了，为什么只弹一个？因为我们只要安排一个会，只需要一间房。

那剩下两个”已结束但没被弹出”的条目留在堆里，会不会让答案多算？不会：

• 它们代表的房间确实已经被分配过了，本来就该计入总数；
• 由于开始时间单调不减，它们在后面的轮次里仍然可以被复用（堆顶总是最小的 end，只要还 <= start 就会被弹）。

所以「懒惰地一次只弹一个」既不多算也不漏用。三间房空着、接着来三个会，就是三轮各弹一个，全部复用上，堆大小不变。

（3）为什么最终 size 就是答案，不用记录过程中的最大值

每一轮最多弹 1 个、必定压 1 个，所以堆的大小只增不减。既然单调不减，终值就是最大值，不需要额外维护 res = max(res, pq.size())。

这正是写法二省掉 res 变量的秘诀：它把「记录历史最大值」偷换成了「让堆大小自己只增不减」。省了一个变量，代价是语义从「当前重叠数」变成了「已开房间数」。

（4）桥：为什么「开了几间房」等于「最大同时重叠数」

这是把本题的两种说法（模拟分配 vs 求最大重叠数）对上的那一环。

堆大小什么时候 +1？只在 start < pq.top() 的时候——也就是连最早结束的那间都还没空。而堆顶是最小的 end，所以：

start < 堆顶（最小 end）
  等价于 start 小于堆里所有的 end
  等价于 已开的每一间房此刻都还在用
  等价于 此刻同时进行的会议数 = 已开房间数 + 1     ← 创了新高

所以堆大小每 +1，就精确对应一次「同时重叠数刷新纪录」。反过来，能复用（start >= 堆顶）时堆大小不变，说明重叠数没有超过历史最高。

堆大小的增长史，就是最大重叠数的刷新史。终值 = 刷新次数 = 最大同时重叠数 = 答案。

也就是说，堆解法并不是在解另一个问题，它是一边分配房间、一边把最大重叠数数出来。

（5）>= 不能写成 >

[[1,5],[5,10]] 应该共用一间，答案是 1；写成 > 就会判成要新开一间，答案变成 2。

另外，为什么必须按开始时间排序：因为要按时间顺序处理会议的到达。判断”此刻有没有房间空着”，前提是”此刻”有意义——若不排序，后来处理的会议可能开始得更早，start >= pq.top() 这个比较就失去含义了。而且正是「start 单调不减」这个性质，保证了上面第（2）点里那句”残留条目后面仍可被复用”。排序不只是为了顺序，它是第（2）点成立的前提。

写法三：事件排序（扫描线）

int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<pair<int,int>> ev;
    for (auto& it : intervals) {
        ev.push_back({it[0], +1});      // 开始，占用 +1
        ev.push_back({it[1], -1});      // 结束，释放 -1
    }
    sort(ev.begin(), ev.end());         // 同一时刻，-1 自动排在 +1 前（因为 -1 < 1）
    int cur = 0, res = 0;
    for (auto& [t, d] : ev) { cur += d; res = max(res, cur); }
    return res;
}

这个写法把「答案 = 最大同时重叠数」直接表达出来了，而且同一时刻 −1 排在 +1 之前恰好就是「相接可复用」那个等号约定——不用额外处理。

写法一其实就是写法三的堆实现：那个 while 弹出对应「处理掉所有 −1 事件」，push 对应一个 +1 事件，res 对应扫描线里 cur 的峰值。三种写法本质是一件事，区别只在语义摆在明面上还是藏起来。

也可以把起点和终点各排一个数组，双指针推进：starts[i] < ends[j] 时 cur++，否则 cur--。这里用严格 < 是同一个道理。

1094. Car Pooling

题意：车的容量为 capacity，给出若干行程 [人数, 上车点, 下车点]，车只能向前开，判断能否完成所有行程。

解：坐标范围很小（0 到 1000），直接用差分数组，不需要排序或堆。

bool carPooling(vector<vector<int>>& trips, int capacity) {
    int diff[1001] = {0};
    for (auto& t : trips) {
        diff[t[1]] += t[0];      // 上车点加人
        diff[t[2]] -= t[0];      // 下车点减人
    }
    int cur = 0;
    for (int i = 0; i <= 1000; i++) {
        cur += diff[i];
        if (cur > capacity) return false;
    }
    return true;
}

在下车点 t[2] 处就把人减掉，正好体现「到站即下车、同一点可以先下后上」，又是那个等号约定。

差分数组和事件排序的关系：两者是同一件事的两种实现。坐标范围小且是整数就用差分数组，O(值域)；坐标范围大或是浮点就拆事件排序，O(NlogN)。

类型四：轮廓随扫描变化 —— 扫描线 + 堆

218. The Skyline Problem

和 253 是同一个家族：沿 x 轴扫描，用堆维护「当前活跃的所有高度」，每次堆顶变化就产生一个关键点。区别是 253 只关心活跃集合的大小，218 关心活跃集合的最大值。

详见《总结（十一）》218 题。

类型五：区间带权求最优 —— DP + 二分

1235. Maximum Profit in Job Scheduling

按结束时间排序，dp[i] 表示只考虑前 i 个工作的最大利润，转移时用 upper_bound 找出「结束时间不超过当前开始时间的工作数 k」，然后 dp[i] = max(dp[i-1], dp[k] + profit)。

这题与 435 的分水岭只有一个字：权重。435 每个区间等权（删一个就是删一个），贪心成立；1235 带 profit，贪心立刻崩——一个 profit=100 的长活能打过一堆 profit=1 的小活。

等权则贪心，带权则 DP。

反过来看，435 就是 1235 中所有 profit 都等于 1 的特例。详见《总结（十三）》。

类型六：两个有序区间列表求交 —— 双指针

986. Interval List Intersections

题意：给出两个各自有序且内部不重叠的区间列表，求它们的交集列表。

解：双指针各指一个列表。两个区间的交集是 [max(起点), min(终点)]，如果 起点 <= 终点 就是一个有效交集。然后移动结束更早的那个指针——因为它不可能再和对面后面的区间有交集了。

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> res;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size()) {
        int lo = max(A[i][0], B[j][0]);
        int hi = min(A[i][1], B[j][1]);
        if (lo <= hi) res.push_back({lo, hi});
        if (A[i][1] < B[j][1]) i++; else j++;     // 结束早的那个先退休
    }
    return res;
}

「移动结束更早的那个」这个动作，和 11、42 里「移动矮的那根」是同一种论证：被移动的那个已经把它的潜力用尽了（它的终点是瓶颈，对面再往后都够不着它），可以安全退休。见《总结（二十二）》第九节。

方法归类：贪心、计数、还是 DP

区间题很容易被笼统地叫成「贪心」，但三类的方法本质不同，判据是「有没有会影响答案的选择」：

判别方法很简单：问自己「换一个做法，答案会变吗」。

• 435 里换一个区间留下 → 答案会变 → 真贪心
• 253 里换一间空闲房间用 → 答案不变 → 不是贪心，只是在数一个量

速查表

蓝图三问

看到一道新的区间题，依次问：

1. 在问什么？ 合并／最多留几个不重叠／最多叠几层／轮廓／带权最优／求交集。认出类别，方法就定了。
2. 按哪一端排序？ 合并按左端；贪心和带权 DP 按右端；求最大重叠数干脆拆成事件不保留区间。
3. 相接算不算重叠？ 拿 [1,2] 和 [2,3] 去问一遍题目，定下是 < 还是 <=。这一族每道题都要单独确认，别靠记忆。

• 上一篇
  Leetcode按题目类型总结（二十二）