区间问题汇总

摘要: 本文总结了 leetcode 上的区间问题相关的题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

力扣上 2000 以内的区间类的题一共 41 道题，按解决方案和问题模型分类。区间类的题有双指针、贪心、平衡树、扫描线四种主流算法。

刷完这些题，力扣上区间类的问题可以算是刷爆了。

$1 双指针

• 163. 缺失的区间
• 228. 汇总区间
• 986. 区间列表的交集
• 495. 提莫攻击

$2 贪心

问题模型1：区间合并

题目	备注
56. 合并区间	区间合并组件，贪心排序，扫描线
57. 插入区间	贪心排序，区间合并
616. 给字符串添加加粗标签	枚举单词而非区间，找到所有满足条件区间(kmp求所有匹配位置)，然后区间合并
758. 字符串中的加粗单词	-

问题模型2：区间覆盖

题目	备注
45. 跳跃游戏 II / 55. 跳跃游戏
763. 划分字母区间	先生成区间，再区间合并
330. 按要求补齐数组
1024. 视频拼接
1326. 灌溉花园的最少水龙头数目
798. 得分最高的最小轮调

问题模型3：区间不相交选择

题目	备注
435. 无重叠区间	贪心排序
759. 员工空闲时间
1353. 最多可以参加的会议数目	在堆上维护贪心，枚举左端点范围，把对应的区间倒进堆里
1520. 最多的不重叠子字符串

问题模型4：区间图着色

题目	备注
252. 会议室	贪心排序
253. 会议室 II	贪心排序，扫描线

问题模型5：区间选点

题目	备注
452. 用最少数量的箭引爆气球	贪心排序
757. 设置交集大小至少为2	平衡树上维护贪心

$3 平衡树

题目	备注
352. 将数据流变为多个不相交区间	平衡树
436. 寻找右区间	平衡树
715. Range 模块	平衡树，可以作为动态维护区间的组件
1288. 删除被覆盖区间	平衡树，顺序遍历树中的区间时，隐含了扫描线的思想
729. 我的日程安排表 I
699. 掉落的方块	主要参考 lc715 的删除，求 r 用 lower_bound 而不是 lc715 中的 upper_bound

$4 扫描线

题目	备注
1229. 安排会议日程 759. 员工空闲时间 253. 会议室 II 2446. 判断两个事件是否存在冲突	扫描线算法处理一系列区间上的统计问题
56. 合并区间
218. 天际线问题	平衡树 multiset 维护 Event
391. 完美矩形	Event 上保存区间，扫描线上的区间用平衡树维护区间的插入删除，保存合并后的区间(lc715)
1094. 拼车	Event 上保存区间，扫描线上的区间用平衡树维护区间的插入删除，保存原始区间
836. 矩形重叠
731. 我的日程安排表 II	Event 上保存区间，线扫过时调用区间插入
850. 矩形面积 II
1272. 删除区间
1288. 删除被覆盖区间
632. 最小区间	在有序 Event 数组上双指针
732. 我的日程安排表 III	扫描线+平衡树$O(N^{2})$；用线段树的话 $O(\log(1e9)N)$

---