leetcode56之合并区间

题目描述：

给出一个区间的集合，请合并所有重叠的区间。

示例：

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[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]]

一点思考：

本题在解答过程中重点考察了二维数组索引求值。另外一点，当遇到循环比较数组（列表）前后两元素数值时，可以定义一个空的列表，用来动态存放数组中另一个待比较元素，这样实现起来更方便。当放入第一个元素时，采用方法二明显更方便一点，值得借鉴。方法一稍显得麻烦一点。