leetcode 重叠区间问题

向右看齐 2022-02-04 06:15 321阅读 0赞

重叠区间问题可以总结为在坐标轴上若干个位置为 (start(i),end(i))的区间，要求求解这些区间中有多少个不重叠区间，或者合并重叠的区间。

leetcode有大神总结了通用模板，[点这里 ][Link 1]

该问题分两类：第一类求重叠区间个数（leetcode 452，435），第二类求合并后的区间（leetcode 56，763）。

对于第一类问题，通常按照end排序，维护一个end变量即可。

低于第二类问题，通常按照start排序，维护一个数组，每次取最后一个数作为比较的标准。

注意按照start或者end排序两种方式都可以求解，只是在不同情况下用其中之一代码编写更简洁。

本文总结了leetcode中重叠区间问题的题目，涉及到的题目如下：

[leetcode 56 合并区间][leetcode 56]

[leetcode 452 射气球][leetcode 452]

[leetcode 435 无重叠区间][leetcode 435]

[leetcode 763 划分字母区间][leetcode 763]

452

题目描述：每个坐标表示气球存在的区间，要求用最少的箭（射箭方向垂直坐标轴 ）射完所有的气球。

输入:
    [[10,16], [2,8], [1,6], [7,12]]
    
    输出:
    2
    
    解释:
    对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 </td> 
 <td> <code>def</code>&nbsp;<code>findMinArrowShots(</code><code>self</code><code>, points):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:type points: List[List[int]]</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:rtype: int</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code><code>&lt;br&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code># 按照end排序，更推荐的方法</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>res</code><code>=</code><code>0</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>end</code><code>=</code><code>float</code><code>(</code><code>'-inf'</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>p&nbsp;</code><code>in</code>&nbsp;<code>sorted</code><code>(points,key</code><code>=</code><code>lambda</code>&nbsp;<code>x: x[</code><code>1</code><code>]):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>p[</code><code>0</code><code>]&gt;end:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>res</code><code>+</code><code>=</code><code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>end</code><code>=</code><code>p[</code><code>1</code><code>]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>res</code> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 </td> 
 <td> <code>def</code>&nbsp;<code>findMinArrowShots(</code><code>self</code><code>, points):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:type points: List[List[int]]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:rtype: int</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code># 按照start排序</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>res,shoot</code><code>=</code><code>0</code><code>,</code><code>float</code><code>(</code><code>'inf'</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>s,e&nbsp;</code><code>in</code>&nbsp;<code>sorted</code><code>(points,reverse</code><code>=</code><code>True</code><code>):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>shoot&gt;e:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>res</code><code>+</code><code>=</code><code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>shoot</code><code>=</code><code>s</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>res</code> </td> 
 </tr> 
 </tbody> 
</table>

435

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

1.  可以认为区间的终点总是大于它的起点。
2.  区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]
    
    输出: 1
    
    解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]
    
    输出: 2
    
    解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]
    
    输出: 0
    
    解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 </td> 
 <td> <code>def</code>&nbsp;<code>eraseOverlapIntervals(</code><code>self</code><code>, intervals):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:type intervals: List[Interval]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:rtype: int</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans&nbsp;</code><code>=</code>&nbsp;<code>0</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>end&nbsp;</code><code>=</code>&nbsp;<code>float</code><code>(</code><code>'-inf'</code><code>)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>p&nbsp;</code><code>in</code>&nbsp;<code>sorted</code><code>(intervals,key</code><code>=</code><code>lambda</code>&nbsp;<code>x:x.end):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>p.start&gt;</code><code>=</code><code>end:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>end</code><code>=</code><code>p.end</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans</code><code>+</code><code>=</code><code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>ans</code> </td> 
 </tr> 
 </tbody> 
</table>

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 </td> 
 <td> <code># Definition for an interval.</code> <code># class Interval(object):</code> <code>#&nbsp;&nbsp;&nbsp;&nbsp; def __init__(self, s=0, e=0):</code> <code>#&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; self.start = s</code> <code>#&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; self.end = e</code> &nbsp; <code>class</code>&nbsp;<code>Solution(</code><code>object</code><code>):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>def</code>&nbsp;<code>merge(</code><code>self</code><code>, intervals):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:type intervals: List[Interval]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:rtype: List[Interval]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code><code>&lt;br&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code># 按照 start排序，对于输入[[2,3],[4,5],[6,7],[8,9],[1,10]],排序后为[[1,10],[2,3],[4,5],[6,7],[8,9]],只需要取ans最后一个数比较</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans</code><code>=</code><code>[]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>p&nbsp;</code><code>in</code>&nbsp;<code>sorted</code><code>(intervals,key</code><code>=</code><code>lambda</code>&nbsp;<code>x: x.start):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>ans&nbsp;</code><code>and</code>&nbsp;<code>p.start&lt;</code><code>=</code><code>ans[</code><code>-</code><code>1</code><code>].end:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans[</code><code>-</code><code>1</code><code>].end</code><code>=</code><code>max</code><code>(ans[</code><code>-</code><code>1</code><code>].end,p.end)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans.append(p)</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>ans</code> </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 </td> 
 <td> <code>def</code>&nbsp;<code>merge(</code><code>self</code><code>, intervals):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:type intervals: List[Interval]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:rtype: List[Interval]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code># 按照end排序，对于[[2,3],[4,5],[6,7],[8,9],[1,10]],需要将入栈的结果一一弹出</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans</code><code>=</code><code>[]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>p&nbsp;</code><code>in</code>&nbsp;<code>sorted</code><code>(intervals,key</code><code>=</code><code>lambda</code>&nbsp;<code>x: x.start):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>ans&nbsp;</code><code>and</code>&nbsp;<code>p.start&lt;</code><code>=</code><code>ans[</code><code>-</code><code>1</code><code>].end:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans[</code><code>-</code><code>1</code><code>].end</code><code>=</code><code>max</code><code>(ans[</code><code>-</code><code>1</code><code>].end,p.end)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans.append(p)&nbsp;</code><code># ans+=p, # 另一种写法，其中p加逗号变为tuple，列表可以用+=将tuple加入其中</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>ans</code> </td> 
 </tr> 
 </tbody> 
</table>

763

题目描述：对于给定的字符串（组成为小写字母），划分为n个子串，要求每个字母最多只出现在一个子串中。输出子串的长度。

例子：

输入：S = "ababcbacadefegdehijhklij"

输出：\[9,7,8\]

描述：划分子串为 "ababcbaca", "defegde", "hijhklij"

两种方法：

1. 暴力的搜索，O(n2)

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 </td> 
 <td> <code>def</code>&nbsp;<code>partitionLabels(</code><code>self</code><code>, S):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sizes&nbsp;</code><code>=</code>&nbsp;<code>[]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code>&nbsp;<code>S:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>i&nbsp;</code><code>=</code>&nbsp;<code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code>&nbsp;<code>set</code><code>(S[:i]) &amp;&nbsp;</code><code>set</code><code>(S[i:]):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>i&nbsp;</code><code>+</code><code>=</code>&nbsp;<code>1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sizes.append(i)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>S&nbsp;</code><code>=</code>&nbsp;<code>S[i:]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>sizes</code> </td> 
 </tr> 
 </tbody> 
</table>

2. 用哈希表记录每个字符第一次出现和最后一次出现的位置，将问题转换为重叠区间的问题

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 </td> 
 <td> <code>def</code>&nbsp;<code>partitionLabels(</code><code>self</code><code>, S):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:type S: str</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>:rtype: List[int]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>"""</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>dic</code><code>=</code><code>{}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>i,s&nbsp;</code><code>in</code>&nbsp;<code>enumerate</code><code>(S):</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>s&nbsp;</code><code>not</code>&nbsp;<code>in</code>&nbsp;<code>dic:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>dic[s]</code><code>=</code><code>[i,i]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>dic[s][</code><code>1</code><code>]</code><code>=</code><code>i</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>dx</code><code>=</code><code>sorted</code><code>(dic.values())</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans</code><code>=</code><code>[]</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>d&nbsp;</code><code>in</code>&nbsp;<code>dx:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>ans&nbsp;</code><code>and</code>&nbsp;<code>ans[</code><code>-</code><code>1</code><code>][</code><code>1</code><code>]&gt;d[</code><code>0</code><code>]:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans[</code><code>-</code><code>1</code><code>][</code><code>1</code><code>]&nbsp;</code><code>=</code>&nbsp;<code>max</code><code>(ans[</code><code>-</code><code>1</code><code>][</code><code>1</code><code>],d[</code><code>1</code><code>])</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>else</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ans.append(d)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>[d[</code><code>1</code><code>]</code><code>-</code><code>d[</code><code>0</code><code>]</code><code>+</code><code>1</code>&nbsp;<code>for</code>&nbsp;<code>d&nbsp;</code><code>in</code>&nbsp;<code>ans]</code> </td> 
 </tr> 
 </tbody> 
</table>

[Link 1]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/discuss/93735/A-Concise-Template-for-%22Overlapping-Interval-Problem%22
[leetcode 56]: https://leetcode.com/problems/merge-intervals/
[leetcode 452]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
[leetcode 435]: https://leetcode.com/problems/non-overlapping-intervals/
[leetcode 763]: https://leetcode.com/problems/partition-labels/