区间问题
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
length = len(intervals)
intervals.sort(key=lambda x:x[0])
res = []
res.append(intervals[0])
for i in range(1,length):
x,y = intervals[i][0],intervals[i][1]
if x > res[-1][1] : # 当前区间的x比res中最后一个区间的y要大，说明无重合的地方
res.append(intervals[i])
else:
res[-1][1] = max(res[-1][1],y)
return res
上面这一道题目巧妙的地方在于，先对所有区间的x值进行排序，所以才会有后来的：每次要加入新的区间的时候，只需要比较前面已经合并完的区间的最后一个区间与当前待加入区间，而无需再比较之前的区间了。
我一开始的想法很复杂，先两两合并后面再对合并结果再合并。这样迭代次数就是动态的不可掌握的，所以思路很重要，这大概就是算法题强调的东西吧。
