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

leetcode有大神总结了通用模板，点这里

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

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

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

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

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

452

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

输入:

[[10,16], [2,8], [1,6], [7,12]]

输出:

2

解释:

对于该样例，我们可以在x = 6(射爆[2,8],[1,6]两个气球)和 x = 11(射爆另外两个气球)。

def findMinArrowShots(self, points):

"""

:type points: List[List[int]]

:rtype: int

"""

# 按照end排序，更推荐的方法

res=0

end=float('-inf')

for p in sorted(points,key=lambda x: x[1]):

if p[0]>end:

res+=1

end=p[1]

return res

def findMinArrowShots(self, points):

"""

:type points: List[List[int]]

:rtype: int

"""

# 按照start排序

res,shoot=0,float('inf')

for s,e in sorted(points,reverse=True):

if shoot>e:

res+=1

shoot=s

return res

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

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

def eraseOverlapIntervals(self, intervals):

"""

:type intervals: List[Interval]

:rtype: int

"""

ans = 0

end = float('-inf')

for p in sorted(intervals,key=lambda x:x.end):

if p.start>=end:

end=p.end

else:

ans+=1

return ans

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] 可被视为重叠区间。

# Definition for an interval.

# class Interval(object):

# def __init__(self, s=0, e=0):

# self.start = s

# self.end = e

class Solution(object):

def merge(self, intervals):

"""

:type intervals: List[Interval]

:rtype: List[Interval]

"""

# 按照 start排序，对于输入[[2,3],[4,5],[6,7],[8,9],[1,10]],排序后为[[1,10],[2,3],[4,5],[6,7],[8,9]],只需要取ans最后一个数比较

ans=[]

for p in sorted(intervals,key=lambda x: x.start):

if ans and p.start<=ans[-1].end:

ans[-1].end=max(ans[-1].end,p.end)

else:

ans.append(p)

return ans

def merge(self, intervals):

"""

:type intervals: List[Interval]

:rtype: List[Interval]

"""

# 按照end排序，对于[[2,3],[4,5],[6,7],[8,9],[1,10]],需要将入栈的结果一一弹出

ans=[]

for p in sorted(intervals,key=lambda x: x.start):

if ans and p.start<=ans[-1].end:

ans[-1].end=max(ans[-1].end,p.end)

else:

ans.append(p) # ans+=p, # 另一种写法，其中p加逗号变为tuple，列表可以用+=将tuple加入其中

return ans

763

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

例子：

输入：S = "ababcbacadefegdehijhklij"

输出：[9,7,8]

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

两种方法：

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

def partitionLabels(self, S):

sizes = []

while S:

i = 1

while set(S[:i]) & set(S[i:]):

i += 1

sizes.append(i)

S = S[i:]

return sizes

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

def partitionLabels(self, S):

"""

:type S: str

:rtype: List[int]

"""

dic={}

for i,s in enumerate(S):

if s not in dic:

dic[s]=[i,i]

else:

dic[s][1]=i

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]