友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
Merge Intervals 区间合并
区间合并模式是一个用来处理有区间重叠的很高效的技术。在涉及到区间的很多问题中，通常咱们需要要么判断是否有重叠，要么合并区间，如果他们重叠的话。这个模式是这么起作用的。
给两个区间，一个是 a，另外一个是 b。别小看就两个区间，他们之间的关系能跑出来6种情况。详细的就看图啦。
怎么识别啥时候用合并区间模式呀？
-
当你需要产生一堆相互之间没有交集的区间的时候
-
当你听到重叠区间的时候
435. 无重叠区间 也是一个类似“区间合并”的题目。但这道题是一个贪心模式的题目，需要按照右端点进行排序。
| 特征 | 按左端点排序 | 按右端点排序 |
|---|---|---|
典型问题 |
||
扫描方向 |
前向扫描，处理当前与上一个结果的关系 |
前向扫描，处理当前与上一个选择的关系 |
核心关注点 |
开始时间，确保新区间不会与更早的区间合并 |
结束时间，贪心地选择最早结束的区间 |
另一种思路 |
对于“合并”问题，理论上也可按右端点排序并反向扫描，但更复杂。 |
对于“无重叠”问题，按左端点排序并动态规划也可解，但效率低。 |
为何有差异 |
希望将重叠的“连成一片”。按左端点排序后，重叠的区间会自然地“靠拢”在一起，便于我们像捏橡皮泥一样把它们揉成一团。 |
希望选出尽可能多的“互不侵犯”的区间。按右端点排序后，我们总是优先选择最早“下班”的，这样它占用的时间资源最少，自然能为后续选择提供最大的灵活性。 |
简单记忆 |
想合并成一整块 → 按开始时间排序，看什么时候开始接上。 |
想选择最多的块 → 按结束时间排序，看谁最早结束不碍事。 |