【leetcode100】合并区间

1、题目描述

以数组 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、初始思路

2.1 思路1

先对所有的区间按照start的大小进行排序，之后如果下一个区间的start<=当前区间的end,则说明该区间应该合并处理。合并时应考虑两种情况，如[[1,3],[2,3]]和[[1,5],[2,3]]，因此合并后的区间start为当前区间的start，end应为max(当前区间end,，下一个区间end)。最后，因为先比较大小才将其加入到result，还要注意将最后一个区间加入result中。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        result = []
        intervals.sort()
        cur_interval = intervals[0]
        for interval in intervals[1:]:
            if cur_interval[1] >= interval[0]:
                cur_interval[1] = max(cur_interval[1],interval[1])
            else:
                result.append(cur_interval)
                cur_interval = interval
        result.append(cur_interval)
        return result

2.2 思路2

将第一个区间加入result中，然后用result中最后一个区间与intervals中的区间进行比较，这样所有区间都会直接加到result中，不用额外考虑最后一个区间。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        result = []
        intervals.sort()
        for interval in intervals:
            if not result or result[-1][1] < interval[0]:
                result.append(interval)
            else:
                result[-1][1] = max(result[-1][1],interval[1])
        return result

2.3 思路3

使用left和right双指针，不一步步加入区间，通过移动指针，可将符合的区间直接加入result中。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort()
        result = []
        left, right = intervals[0][0], intervals[0][1]
        for interval in intervals[1:]:
            if right < interval[0]:
                result.append([left,right])
                left = interval[0]
                right = interval[1]
                continue
            if interval[1] > right:
                right = interval[1]
        result.append([left,right])
        return result