Leetcode 56 合并区间

2020-06-27  本文已影响0人  SunnyQjm

合并区间

题目

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

解答

测试验证

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype List[List[int]]

        (Knowledge)

        思路:
        1. 首先对输入的区间数组进行排序;
        2. 接着用两个指针,cur指向当前处理的区间,next指向下一个要处理的区间;
        3. 根据cur和next所指区间的情况,分别处理:
            - intervals[cur] 和 intervals[next]区间没有重叠,则令intervals[cur + 1] = intervals[next], cur++, next++
            - intervals[cur][1] >= intervals[next][0],则令intervals[cur][1] = max(intervals[cur][1], intervals[next][1]), next++
        4. 最后返回intervals[:cur + 1]
        """

        # 首先对输入的区间数组进行排序
        intervals = sorted(intervals)
        cur, next = 0, 1

        while next < len(intervals):
            if intervals[next][0] > intervals[cur][1]:  # 处理没有重叠的情况
                intervals[cur + 1], cur, next = intervals[next], cur + 1, next + 1
            else:  # 处理有重叠的情况
                intervals[cur][1], next = max(intervals[cur][1], intervals[next][1]), next + 1

        return intervals[:cur + 1]


if __name__ == '__main__':
    solution = Solution()
    print(solution.merge([[1, 3], [2, 6], [8, 10], [15, 18]]), "= [[1, 6], [8, 10], [15, 18]]")
    print(solution.merge([[1, 4], [4, 5]]), "= [[1, 5]]")
上一篇下一篇

猜你喜欢

热点阅读