leetcode56之合并区间
题目描述：
给出一个区间的集合，请合并所有重叠的区间。
示例：
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
代码如下：
1 def merge(intervals): 2 ''' 3 4 :param intervals: 5 :return 6 ''' 7 # 根据区间左端点排序 8 intervals.sort(key=lambda x: x[0]) 9 if intervals: 10 res = [intervals[0]] 11 else: 12 return intervals 13 for i in range(1, len(intervals)): 14 # 可以合并 15 if (intervals[i][-1] - intervals[i][0] + res[-1][-1] - res[-1][0]) \ 16 >= intervals[i][-1] - res[-1][0]: 17 res[-1] = [res[-1][0], max(intervals[i][-1], res[-1][-1])] 18 # 不能合并,将intervals当前值放入res中 19 else: 20 res.append(intervals[i]) 21 22 return res 23 24 25 print('--------测试merge()---------') 26 A = [[1, 2], [0, 6], [7, 9], [10, 18]] 27 B = [] 28 res = merge(B) 29 print("res=", res) 30 31 32 def merge1(intervals): 33 ''' 34 35 :param intervals: 36 :return: 37 ''' 38 intervals.sort(key=lambda x: x[0]) 39 res = [] 40 for item in intervals: 41 # 如果res为空 42 if not res: 43 res.append(item) 44 else: 45 # 可以合并 46 if item[0] <= res[-1][1]: 47 res[-1][1] = max(item[1], res[-1][1]) 48 # 不能合并 49 else: 50 res.append(item) 51 52 return res 53 54 55 print("=============测试merge1()==============") 56 result = merge1(A) 57 print("result=", result)
输出：
--------测试merge()--------- res= [] =============测试merge1()============== result= [[0, 6], [7, 9], [10, 18]]
一点思考：
本题在解答过程中重点考察了二维数组索引求值。另外一点，当遇到循环比较数组（列表）前后两元素数值时，可以定义一个空的列表，用来动态存放数组中另一个待比较元素，这样实现起来更方便。当放入第一个元素时，采用方法二明显更方便一点，值得借鉴。方法一稍显得麻烦一点。
