56.MergeIntervals题目来源：https://leetcode-cn.com/problems/merge-intervals题目给定一组区间，请合并所有重叠的区间。示例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]可以视为重叠区间。解题思路：贪心算法首先要理解题意（以例1和例2为例）：例1：例2：上图中线段的比例不是准确的比例，仅作为辅助理解。结合上图和示例输出的结果可以看出，如果合并区间，则两个区间之间一定存在交集。再看例2，交点部分也可以是一个点。同样需要注意的是：这里有一个前提，就是区间需要按照左端点升序排列。给定列表排序后，同时添加结果集，将两者结合判断是否有交集，从而决定是否合并区间。具体算法：对区间进行排序，根据区间的左端点升序排序，然后遍历；如果遍历的区间左端点>结果集中最后一个区间的右端点，说明没有交集，这里直接把区间加到结果集中就可以了；如果遍历的区间左端点<=结果集中最后一个区间的右端点，则存在交集，需要在这里合并区间。具体方法：更新结果集中最后一个区间的右端点（这里取两个区间中较大的值）。对于上面的交集，将最后一个区间的右端点更新为最大值，达到合并更多区间的目的，结果这就是贪心策略。具体实现代码如下：代码实现类解决方案：defmerge(self,intervals:List[List[int]])->List[List[int]]:#对数组进行升序排序，取左端数组元素区间的作为区间.sort(key=lambdax:x[0])#定义返回数组ret=[]#这里合并的依据是区间必须有交集#即左端点一个区间的<=另一个区间的右端点#否则，如果没有交集，就不需要合并#此时一个区间的左端点>另一个区间的右端点#这里主要比较的是排序后的数组区间和返回数组的最后一个区间之间forintervalinintervals:#返回数组为空时，直接将第一个加入数组中#当返回数组不为空时，根据abovebasis#首先看返回的数组是空的，还是区间呢notintersectifnotretorinterval[0]>ret[-1][1]:ret.append(interval)#返回的数组不为空，如果有交集，合并区间#更新右端点返回数组的最后一个区间，取两个区间中较大的值else:ret[-1][1]=max(ret[-1][1],interval[1])returnret得到上面的结果是使用贪心算法的思想。判断区间是否可以合并，需要先对区间进行排序，判断区间之间是否有交集，并据此更新结果集，进而解决《56. 合并区间》问题的主要内容。欢迎关注微信公众号《书所集录》
