56. Merge Intervals

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

https://leetcode.com/problems/merge-intervals/

Example 1:

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

Example 2:

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

Constraints:

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4

Test Cases

1 2	class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('intervals, expected', [
    ([[1,3],[2,6],[8,10],[15,18]], [[1,6],[8,10],[15,18]]),
    ([[1,4],[4,5]], [[1,5]]),

    ([[1,4],[0,4]], [[0,4]]),
    ([[1,4],[2,3]], [[1,4]])
])
class Test:
    def test_solution(self, intervals, expected):
        sol = Solution()
        assert sol.merge(intervals) == expected

Thoughts

按左端点排序所有的区间。

第一个区间就是合并后的第一个区间。任何时候，对于下一个原区间，看跟最后一个合并的区间是否有重叠。如果重叠就合并到一起（右端点取二者较大），否则就形成新的合并区间。

Code

solution.py

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort(key=lambda interval: interval[0])

        merged = [intervals[0]]
        for i in range(1, len(intervals)):
            interval = intervals[i]
            if interval[0] > merged[-1][1]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。