Interview_DS_Algo 区间问题Intervals全攻略从合并、冲突检测到会议室调度与日历预订【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo本文以开源仓库 Interview_DS_Algo 中 Arrays/Intervals_Based_Qn/README.md 的 27 道区间类面试题为骨架系统梳理区间题的五大解题范式排序合并、冲突检测、最少资源分配、双指针求交、有序结构查询并结合仓库内 Merge Intervals.cpp、Meeting Rooms II.cpp 等源码给出可复制、可运行的 C/Java 实现与复杂度分析。读完本文你将掌握区间题的通用分析框架能独立秒杀 LeetCode 区间标签下从 Easy 到 Hard 的主流题目。一、区间问题为什么是面试必考区间Interval通常用二元组[start, end]表示一段连续的时间或坐标范围。它天然贴近现实场景会议室预订、日历排期、航线时刻、事件调度、日程重叠等因此是 Amazon、Google、Microsoft、Uber、Facebook、Snapchat 等公司的高频考点——这一点在仓库每个题解文件头部的Company Tags注释中都有印证例如 Meeting Rooms II.cpp 标注了 Uber、Facebook、Microsoft、Yelp、Google、Snapchat、Amazon、Cisco 八家公司Insert Interval.cpp 标注了 Google、Twitter、Microsoft、Apple、Amazon。从仓库的题目组织可以看出区间题解法高度套路化90% 的题目第一步都是按起点start排序之后再用贪心、双指针、堆优先队列、二分或差分数组解决问题。只要吃透排序 扫描这一核心思想就能举一反三。二、题目全景27 道区间题速查表以下表格完整继承 Arrays/Intervals_Based_Qn/README.md 的题目清单并补充仓库内对应的源码相对路径与核心考点无扩展名的文件为多解法合集题目LeetCode 编号仓库源码路径核心考点Merge Intervals (56)Merge Intervals.cpp排序 贪心合并Non-overlapping Intervals (435)Greedy/Non-overlapping Intervals.cpp贪心同时归入 Greedy 分类Insert Interval (57)Insert Interval.cpp线性扫描 区间插入Meeting Rooms (252)Meeting Rooms.cpp排序后冲突检测Meeting Rooms II (253)Meeting Rooms II.cpp堆 / 双排序最多重叠数Find Right Interval (436)Find Right Interval.cpp二分 /lower_boundCar Pooling (1094)Car Pooling (2 approaches))另见 Line Sweep Technique/Car Pooling.cpp差分 / 排序Remove Covered Intervals (1288)Remove Covered Intervals.cpp排序 覆盖判定Meeting Scheduler (1229)Meeting_Scheduler.cpp双指针求共同空闲Minimum Number of Arrows to Burst Balloons (452)Greedy/Minimum Number of Arrows to Burst Balloons.cpp贪心归入 Greedy 分类The Number of the Smallest Unoccupied Chair (1942)The Number of the Smallest Unoccupied Chair.cpp双堆时间线模拟Interval List Intersections (986)Interval List Intersections.cpp双指针求交集Data Stream as Disjoint Intervals (352)Data Stream as Disjoint Intervals.cpp有序结构维护合并Maximum Number of Events That Can Be Attended II (1751)Maximum Number of Events That Can Be Attended II.cpp排序 DPMeeting Rooms III (2402)Meeting Rooms III.cpp双堆 房间统计My Calendar I (729)My Calendar I.cppsetlower_boundMy Calendar II (731)My Calendar II.cpp另见 Line Sweep Technique/My Calendar II.cpp双区间 差分Divide Intervals Into Minimum Number of Groups (2406)Divide Intervals Into Minimum Number of Groups.cpp堆 / 线扫描Two Best Non-Overlapping Events (2054)Two Best Non-Overlapping Events.cpp排序 DPSpecial Array II (3152)Special Array II.cpp前缀 / 区间查询Maximum Beauty of an Array After Applying Operation (2779)Maximum Beauty of an Array After Applying Operation.cpp排序 滑动窗口Count Days Without Meetings (3169)Count Days Without Meetings.cpp合并后求补集Check if Grid can be Cut into Sections (3394)Check if Grid can be Cut into Sections.cpp二维区间合并Maximum Number of Events That Can Be Attended (1353)Maximum Number of Events That Can Be Attended.cpp贪心 堆Minimum Operations to Make Array Elements Zero (3495)Minimum Operations to Make Array Elements Zero.cpp区间覆盖 / 思维题Set Intersection Size At Least Two (757)Set Intersection Size At Least Two.cpp排序 贪心需要说明的是仓库中部分区间题同时被归类到其他专题目录如 Greedy/Non-overlapping Intervals.cpp、Greedy/Minimum Number of Arrows to Burst Balloons.cpp、Line Sweep Technique/Meeting Rooms II.cpp体现了一道题多种归类视角的学习思路区间题常常是贪心、堆、线扫描、DP 等专题的交叉点。三、范式一排序 合并Merge / Insert / Remove Covered3.1 Merge IntervalsLeetCode 56重叠区间合并Merge Intervals.cpp 给出了两种做法是理解所有区间题的起点。暴力法O(n²)遍历区间 i向后查找与其重叠的 j若!(i_end j_start || i_start j_end)则判定重叠并合并、删除 j若无合并则前进。这种做法在插入/删除时产生 O(n) 的数组搬移容易 TLE仅作思维热身。排序法O(n log n)按起点排序后只需一遍线性扫描class Solution { public: vectorvectorint merge(vectorvectorint intervals) { sort(begin(intervals), end(intervals)); // 按起点排序 vectorvectorint result; result.push_back(intervals[0]); for (int i 1; i intervals.size(); i) { int curr_start intervals[i][0]; int curr_end intervals[i][1]; // 无重叠直接加入结果 if (curr_start result.back()[1]) { result.push_back(intervals[i]); } else { // 有重叠延长当前区间的右端点 result.back()[1] max(result.back()[1], curr_end); } } return result; } };复杂度T.C O(n log n)排序主导S.C O(n)结果数组。文件内同时附有 Java 版本核心逻辑一致仅需把sort换成Arrays.sort(intervals, (a,b) - Integer.compare(a[0], b[0]))。注意判重边界curr_start result.back()[1]表示仅当起点严格大于上一个区间的终点才视为无重叠即端点相接不算重叠[1,2]与[2,3]合并为[1,3]这是 LeetCode 56 与 Meeting Rooms 系列判断口径差异的关键。3.2 Insert IntervalLeetCode 57在有序区间中插入Insert Interval.cpp 给出 2 种做法。暴力法Approach-1O(n²)直接对原数组做insert/erase同样容易超时。线性法Approach-2O(n)把区间分成三段处理class Solution { public: vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) { int i 0; vectorvectorint result; // 第一段完全在 newInterval 左侧直接复制 while (i intervals.size()) { if (intervals[i][1] newInterval[0]) { result.push_back(intervals[i]); } else if (intervals[i][0] newInterval[1]) { break; // 碰到第一个完全在右侧的区间跳出 } else { // 重叠扩大 newInterval newInterval[0] min(newInterval[0], intervals[i][0]); newInterval[1] max(newInterval[1], intervals[i][1]); } i; } result.push_back(newInterval); // 中间段插入合并后的新区间 while (i intervals.size()) { // 第三段剩余右侧区间 result.push_back(intervals[i]); i; } return result; } };要点由于原区间有序且互不重叠插入逻辑天然可线性完成break的时机选择保证了右侧区间原样保留无需二次排序。3.3 Remove Covered IntervalsLeetCode 1288删除被覆盖区间Remove Covered Intervals.cpp 提供了 3 种做法其排序比较器是精华auto lambda [](vectorint vec1, vectorint vec2) { if (vec1[0] vec2[0]) { return vec1[1] vec2[1]; // 起点相同终点降序长的在前 } return vec1[0] vec2[0]; // 起点升序 };这样排序后result.back()一定是当前最宽的区间只需判断result.back()[1] intervals[i][1]即可决定是否被覆盖。Approach-3 进一步把 O(n) 的结果数组优化为 O(1) 的lastIntervalKaEnd计数把空间复杂度压到常数。这个起点升序、起点相同时终点降序的排序技巧在区间覆盖类问题中非常通用。四、范式二冲突检测Meeting Rooms / My Calendar4.1 Meeting RoomsLeetCode 252能否参加所有会议Meeting Rooms.cpp 是区间题的Hello World题目描述已内嵌在文件头部Premium 题自带题干Given [ [0, 30], [5, 10], [15, 20] ], return false.思路按start排序后只需检查相邻区间是否重叠——currInterval_start prevInterval.end即冲突。仓库给出两种写法Approach-1 用静态比较函数 维护prevIntervalApproach-2 用 lambda 相邻两两比较curr.end next.start则返回 false。注意此处curr.end next.start是允许的前一会议在下一会议开始时恰好结束不冲突与 Merge Intervals 的相接即合并口径互补。复杂度T.C O(n log n)S.C O(1)排序不计。4.2 My Calendar ILeetCode 729日历预订冲突检测My Calendar I.cpp 升级为在线插入 查询冲突给出 3 种做法Approach-1暴力O(n²)遍历已有预订若!(end curr.first || start curr.second)则有重叠返回 false。Approach-2setlower_boundO(n log n)利用有序集合找到第一个起点 ≥ start 的预订分别与后继、前驱检查重叠class MyCalendar { public: setpairint, int st; bool book(int start, int end) { auto it st.lower_bound({start, end}); // 找起点 start 的第一个预订 // 与后继区间冲突 if (it ! st.end() it-first end) return false; // 与前驱区间冲突 if (it ! st.begin()) { auto prevIt prev(it); if (start prevIt-second) return false; } st.insert({start, end}); return true; } };Approach-3setupper_bound插入时把{start, end}反存为{end, start}一次upper_bound即可完成检查代码更短。文件注释还特别提示Java 中可用TreeSet 自定义比较器 ceiling/floor等价实现next[0] end或start prev[1]即冲突。这套有序结构 lower_bound 找邻居的模式是 My Calendar 系列I/II/III与 Data Stream as Disjoint Intervals 的共同底层。五、范式三最少资源分配Meeting Rooms II / 分组 / 会议室 III5.1 Meeting Rooms IILeetCode 253最少会议室数量Meeting Rooms II.cpp 是区间题经典中的经典本质是求最大同时重叠数给出 2 种做法。Approach-1最小堆O(n log n)按开始时间排序后用一个小根堆维护正在使用的会议室按结束时间最小者优先。每来一个新会议若堆顶会议top.end curr.start已结束则弹出复用同一间房否则新开一间priority_queueInterval, vectorInterval, Compare pq; // 按 end 升序 pq.push(intervals[0]); // 至少需要一间 for (int i 1; i n; i) { Interval top pq.top(); Interval curr intervals[i]; if (top.end curr.start) { pq.push(curr); // 冲突需要新房间 } else { pq.pop(); // 最优先结束的会议腾出房间 pq.push(curr); // 复用同一房间 } } return (int)pq.size();源码注释给出了为什么必须按开始时间排序的关键论证排序确保堆中已开始会议的起点无需再被检查堆顶即最早结束者比较结果必然正确。Compare仿函数返回i1.end i2.end实现小根堆语义。Approach-2双排序/时序法O(n log n)把 start 和 end 分别排序双指针扫描——startTime[i] endTime[j]时房间数 1否则 j 前进一间房被释放。这是线扫描思想的雏形也是仓库 Line Sweep Technique 目录含 Line Sweep Technique/Meeting Rooms II.cpp的核心模式。5.2 Divide Intervals Into Minimum Number of GroupsLeetCode 2406Divide Intervals Into Minimum Number of Groups.cpp 与 Meeting Rooms II 完全同构仓库用排序 最小堆一行核心逻辑解决堆内存每组最后一个区间的结束时间若pq.top() start说明某组可容纳当前区间弹出并复用最终pq.size()即最少分组数T.C O(n log n)S.C O(n)。文件注释预告了Line Sweep Algorithm作为第二种解法的方向——该专题的详细讲解见仓库 Line Sweep Technique/README.md。5.3 Meeting Rooms IIILeetCode 2402统计被预订最多的会议室Meeting Rooms III.cpp 是 Google 高频题比 II 更进一步要输出被使用次数最多的最小编号会议室。Approach-1暴力模拟O(m log m m·n)按开始时间排序后对每场会议线性扫描 n 个房间若找到空闲房直接占用否则把会议顺延到最早空闲的房间lastAvailableAt[EarlyEndRoom] (end - start)同时用long long记录房间可用时间避免溢出。Approach-2双堆优化O(m log m m log n)usedRooms按{结束时间, 房间号}小根堆与unusedRooms房间号小根堆协同工作——会议开始时先释放已结束房间再优先使用编号最小的空闲房无空闲时则占用最早结束的房间并顺延其结束时间。用long long存结束时间是本题防溢出细节。从 I 到 III会议室系列完整展示了暴力扫描 → 堆优化的演进路径是学习堆priority_queue在区间调度中应用的绝佳素材仓库 Heap 目录还有更多堆专题题解。六、范式四双指针求交集与共同区间Interval List Intersections / Meeting Scheduler6.1 Interval List IntersectionsLeetCode 986Interval List Intersections.cpp 要求两个各自有序且互不重叠的区间列表求交集双指针一趟完成while (i m j n) { int x max(firstList[i][0], secondList[j][0]); int y min(firstList[i][1], secondList[j][1]); if (x y) result.push_back({x, y}); // 有效交集 if (firstList[i][1] secondList[j][1]) j; else i; }核心技巧[x, y] [max(左端点), min(右端点)]是两个区间交集的通用公式判定x y决定是否产生有效交集谁的右端点小谁先移动保证不遗漏。T.C O(m n)S.C O(1)不含结果。6.2 Meeting SchedulerLeetCode 1229两人的共同空闲时段Meeting_Scheduler.cpp 是 Intersections 的实战变体Google 视频面试改编题题目描述内嵌于文件头部两人各自的空闲时段已知且互不重叠求最早一段时长 ≥ duration 的共同空闲时间。解法与 986 完全同构int start max(slots1[i][0], slots2[j][0]); int end min(slots1[i][1], slots2[j][1]); if (end - start duration) return {start, start duration}; // 否则移动结束时间更早的一方注意返回{start, startduration}而非{start, end}——这是题目预约从 start 开始持续 duration 分钟的要求。无解时返回空数组{}。七、范式五有序结构 二分查询Find Right IntervalFind Right Interval.cpp 一口气给出 4 种做法是从 O(n²) 逐步优化到 O(n log n) 的经典教学案例Approach-1暴力O(n²)对每个区间向后线性找start_j end_i。Approach-2手写二分O(n log n)排序后用mapvectorint, int保存区间 → 原下标配合lower_bound式二分找第一个start target的位置。Approach-3二分 简化 mapO(n log n)利用题目约束每个 start 唯一源码注释专门强调Always focus on each detail of the question改用mapint, int以起点为键省去存储整个区间。Approach-4STLlower_bound收尾O(n log n)最优雅版本for (int i 0; i n; i) { auto end_j mp.lower_bound(intervals[i][1]); // 第一个 start end_i if (end_j ! end(mp)) { result[i] end_j-second; } }本题的价值在于展示当题目给出每个起点唯一这类约束时一定要利用它简化数据结构——这是区间题中常见的出题人善意提示。八、范式六事件时间线模拟Smallest Unoccupied Chair / Count Days Without Meetings8.1 The Number of the Smallest Unoccupied ChairLeetCode 1942The Number of the Smallest Unoccupied Chair.cpp 给出 3 种做法是把到达/离开事件流模拟的教科书题Approach-1暴力O(n²)endTimes[i]记录每个椅子的释放时间到达时线性找第一个endTimes[i] arrival的空椅。Approach-2双堆O(n log n)occupied堆存{离开时间, 椅子号}free堆存空椅子号。每位朋友到达时先把所有occupied.top().first arrival的椅子释放进free有free则取编号最小者否则分配新椅子。借助到达时间互不相同这一约束用targetArrivalTime精确识别目标朋友。Approach-3小根堆 有序集合setint保证取到编号最小的可用椅子。双堆模式一个管谁先结束一个管谁最空闲是区间调度模拟题Meeting Rooms III、Maximum Number of Events 等的通用底座。8.2 Count Days Without MeetingsLeetCode 3169与同类补集题Count Days Without Meetings.cpp 的思路是先对会议区间排序、合并重叠再统计合并后区间之间的空隙天数与之互补的 Check if Grid can be Cut into Sections.cppLeetCode 3394把一维合并扩展到二维网格的行/列切割可行性判断。Maximum Beauty of an Array After Applying Operation.cpp2779则将区间思想与滑动窗口结合每个元素可变换为区间[x-k, xk]求最大重叠区间长度。九、进阶排序 DP 与贪心堆组合区间题的上限在于与 DP、贪心的结合Maximum Number of Events That Can Be Attended II.cpp1751按结束时间排序后做选/不选的 0-1 型 DP利用二分定位前一个不冲突事件是区间 DP的典型模板。Two Best Non-Overlapping Events.cpp2054排序后维护前缀最大价值配合二分或双指针找可拼接的第二个事件。Greedy/Non-overlapping Intervals.cpp435经典贪心按结束时间最早优先删除使区间互不重叠的最少区间数。Greedy/Minimum Number of Arrows to Burst Balloons.cpp4523 种解法按右端点排序后一支箭尽可能多地戳破重叠气球。Maximum Number of Events That Can Be Attended.cpp1353按开始时间分组 最小堆取结束时间最早的会议是贪心 堆调度标杆。Set Intersection Size At Least Two.cpp757与Minimum Operations to Make Array Elements Zero.cpp3495则是区间思想的思维延伸题。十、学习方法与仓库使用建议按范式刷题建议按照本文的六大范式顺序刷——先 Merge Intervals合并、Meeting Rooms冲突检测、Meeting Rooms II资源分配、Interval List Intersections双指针、Find Right Interval二分、Smallest Unoccupied Chair时间线模拟再挑战 DP/贪心进阶题。关注多解法文件仓库中 Insert Interval.cpp、Find Right Interval.cpp、Remove Covered Intervals.cpp 等文件同时提供 24 种解法和 C/Java 双语实现适合对照学习从暴力到最优的优化轨迹每个文件头部的T.C/S.C注释可直接用于面试复杂度叙述。交叉目录学习区间题散落在 Greedy、Heap、Line Sweep Technique、Stack 等多个专题目录中建议配合各目录的 README如 Line Sweep Technique/README.md交叉阅读建立一题多解、多题一解的知识网络。面试要点提炼区间题的通用答法四步曲——(1) 判断是否需排序(2) 确定重叠判据start_i end_prev还是start_i end_prev取决于端点是否闭合(3) 选择扫描工具贪心 / 堆 / 双指针 / 二分 / 差分(4) 明确复杂度。遇到在线查询变体时立刻想到有序结构set/maplower_bound遇到时间线模拟时想到双堆。十一、总结区间问题看似题型繁多实则万变不离其宗排序建立序关系扫描维护状态堆/二分/双指针加速决策。Interview_DS_Algo 仓库的 Arrays/Intervals_Based_Qn 目录用 27 道覆盖 Easy 到 Hard 的真题加上每个文件内嵌的题目描述Premium 题、公司标签、多语言多解法实现和复杂度注释构成了一套完整的区间题训练闭环。吃透这份清单再遇到任何合并、插入、重叠、调度、预订、分组类题目都能迅速归入对应范式并给出最优解。【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考