算法题--合并区间

image.png

0. 链接

题目链接

1. 题目

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

2. 思路1：先按照左端点排序+再逐个合并区间

1. 按照各个区间左端值升序排列，再从左到右合并两个相邻区间，遇到不能合并的，则收集到结果里；否则修改区间右端点值

3. 代码

# coding:utf8
from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) <= 1:
            return intervals

        intervals.sort(key=lambda x: x[0], reverse=False)

        last_idx = 0

        for i in range(1, len(intervals)):
            last_interval = intervals[last_idx]
            interval = intervals[i]
            if interval[0] <= last_interval[1] <= interval[1]:
                last_interval[1] = interval[1]
            elif last_interval[1] < interval[0]:
                last_idx += 1
                last_interval = intervals[last_idx]
                last_interval[0] = interval[0]
                last_interval[1] = interval[1]

        return intervals[:last_idx + 1]


solution = Solution()
print(solution.merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(solution.merge([[1,4],[4,5]]))
print(solution.merge([]))
print(solution.merge([[1, 4], [0, 1]]))

输出结果

[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[]
[[0, 4]]

4. 结果

image.png