leetcode回顾——Merge Intervals

LeetCode

题目

1
2
3
4
5
6
7
8
9
10
11
12
给出一个区间的集合，请合并所有重叠的区间。

示例 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
3
                1--2--3--4--5--6--7--8--9
区间一：[2,3]       [---]    
区间二：[5,6]                [---]

第二种 部分相交

1
2
3
                1--2--3--4--5--6--7--8--9
区间一：[2,5]       [--------]    
区间二：[4,6]             [------]

第三种 包含

1
2
3
                1--2--3--4--5--6--7--8--9
区间一：[2,8]       [------------------]    
区间二：[4,6]             [------]

因此，只需要理清这三种关系中，每个区间的左右两个端点的值的大小关系就能解出这道题了。

为了能够一次遍历实现区间合并，还需要对参数intervals进行一些操作，利用lambda表达式设置排序的比较对象，使得元素排序根据区间的左端点的大小进行升序排序，然后就按上面的三种情况进行仔细区分分析就可以了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if len(intervals) <= 1:
            return intervals
        intervals.sort(key=lambda x: x.start)
        a = 0; b = 1
        while a < len(intervals):
            if b == len(intervals):
                a += 1
                b = a + 1
                continue
            t_1 = intervals[a]
            t_2 = intervals[b]
            if t_1.end >= t_2.start:
                intervals[a].end = max(t_1.end, t_2.end)
                intervals.pop(b)
            else:
                a += 1
                b += 1
        return intervals