给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
这题我采用类似于 插入排序 的思路：将输入的列表分为两个部分（“有序部分”、“无序部分”），开始时“有序部分”为空，“无序部分”为输入列表；把“无序部分”的元素依次插入“有序部分”中，当“无序部分”为空时，“有序部分”就是排序好的列表。
因为这题的操作会导致列表元素个数的变化，不能单纯的把输入列表分为两部分，而是维护一个 合并列表 combined 来用来存储完成操作的元素，依次把输入列表 intervals 中的元素插入到 combined 中并完成合并操作。
每次向 combined 中插入元素时，都要保证：
combined 中每个元素代表的区间之间不能有重叠combined 中每个元素代表的区间按顺序排列，即是有序的这样重点就在于如何正确地向 combined 中插入元素，并能满足上面两个条件。对于插入元素 new 都进行以下操作：
combined 中的元素 combined[i]，判断以下情形：
combined[i] 与 new 重叠，则把 new 并入 combined[i] 中。由于 combined[i] 区间有变化，需要检测周围区间是否出现重叠，由于 combined 列表是有序的，所以重叠区域只能出现在右侧，则向右遍历，合并重叠区间。完成合并操作后跳出遍历。new 的区间上界已经小于了 combined[i] 的下界，由于 combined 列表是有序的，说明 combined 中没有与 new 重叠的区间，则把 new 插入到 combined 的合适位置（就是 i 位置）。跳出遍历。combined 后，new 依然没有插入到合适位置，说明 combined 的区间都小于 new，那就把它放在 combined 最后。对输入列表 intervals 中每个区间都依次插入 combined 后，区间的合并任务就完成了。
本解法 Python 代码如下
class Solution(object):
def add_inter(self, master, new):
i = 0
while i < len(master):
if max(new[0], master[i][0]) <= min(new[1], master[i][1]): # 出现重叠区间
master[i] = [min(new[0], master[i][0]), max(new[1], master[i][1])]
right = master[i][1]
to_remove = []
for mj in master[i + 1:]: # 向右检测并合并重叠区间
if right >= mj[0]:
right = max(right, mj[1])
to_remove.append(mj)
else:
break
master[i][1] = right
for r in to_remove:
master.remove(r)
break
elif new[1] < master[i][0]: # 无重叠区间，把 new 插入到合适位置，即 i 位置
master.insert(i, new)
break
i += 1
if i == len(master): # 遍历完还没有被插入，则放在最后
master.append(new)
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
combined = []
for inter in intervals:
self.add_inter(combined, inter) # 依次向 combined 插入区间
return combined