重叠区间问题

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

常见题型：

• 合并区间：

 leetcode 56（合并区间）leetcode 763（先统计，再合并区间）

• 计算不重叠区间的个数：

   leetcode 435（不重叠区间个数）leetcode 452（相邻区间视为重叠区间）

合并区间问题

1、对数列的按首元素排序
2、得到初始数列 init=nums[0]
3、判断初始数列的末尾元素 init[−1] 和数列第 i 项元素的首元素nums[i][0] 的大小关系

• init[−1]>nums[i][0]:区域相交：init=[init[0],max(nums[i][1],init[−1])]
• init[−1]<=nums[i][0]:得到不相交的区间，更新 init=nums[i][0]

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。

解题思路

对于合并数组的问题，通常按照start排序，维护一个数组，每次取最后一个数作为比较的标准。如果后面加进来的区间的start的大小比之前区间的end还要小，表示二者有相交。修改原区间为 init=[init[0],max(nums[i][1],init[−1])]；否则不相交，将其添加至res数组中。

class Solution(object):def merge(self, intervals):""":type intervals: List[List[int]]:rtype: List[List[int]]"""if intervals==[]:return []# 按start排序 intervals.sort(key=lambda x:x[0]) res = []for i in range(len(intervals)):if res!=[] and intervals[i][0]<=res[-1][1]:res[-1][1] = max(res[-1][1], intervals[i][1])else:res.append(intervals[i])return res 

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

解题思路

本题也是合并区间，不过需要转换思路，先用哈希表记录每个字符第一次出现和最后一次出现的索引位置。然后对其进行按第一项排序，，最后变为合并子区间的问题。

class Solution:def partitionLabels(self, S: str) -> List[int]:# 先用哈希表记录每个字符第一次出现和最后一次出现的位置，将问题转为重叠区间的问题dic = {}for i, s in enumerate(S):if s not in dic:dic[s] = [i, i]else:dic[s][1] = i # 将哈希表中所有的values排序，按第一项排序dx = sorted(dic.values())ans = []for d in dx:if ans!=[] and ans[-1][1]>d[0]:ans[-1][1] = max(ans[-1][1], d[1])else:ans.append(d)return [d[1] - d[0] + 1 for d in ans]

计算不重叠区间的个数

1、对数列按末尾元素排序
2、得到初始数列init=nums[0]
3、判断初始数列的末尾元素 init[−1] 和数列第 i 项元素的首元素 nums[i][0] 的大小关系

• init[−1]>nums[i][0]:区域相交，跳过该区域，所以init=nums[i]，并计数
• init[−1]<=nums[i][0]:不重叠的区间，继续遍历

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路

1、从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
2、把所有与 x 区间相交的区间从区间集合 intvs 中删除。
3、重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

code block【————】               ：我们选取的最早结束的区间【————】          ：有重叠的可能区间A
【————————————————】      ：有重叠的可能区间B
假设可能区间A或B参与形成了最长序列，那么A，B之后的区间必然可以与我们选取的区间组合形成最长序列，
所以完全可以去掉A，B（如果有的话）

class Solution(object):def eraseOverlapIntervals(self, intervals):""":type intervals: List[List[int]]:rtype: int"""res = 0 intervals.sort(key=lambda x:x[1])end = -float('inf')for interval in intervals:if interval[0]<end:res += 1 else:end = interval[1]return res 

452. 用最少数量的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。
由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。
平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 
xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

解题思路

按照end排序

class Solution(object):def findMinArrowShots(self, points):""":type points: List[List[int]]:rtype: int"""res = 0 end = -float('inf')points.sort(key=lambda x: x[1])# print(points)for p in points:if p[0]>end:res += 1 end = p[1]return res