Merge Intervals

Problem

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

Given an array of intervals where intervals[i] = [start:sub:`i`, end:sub:`i`], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

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.

Example 3:

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

Constraints:

1 <= intervals.length <= 10:sup:`4`
intervals[i].length == 2
0 <= start:sub:`i`<= end:sub:`i`<= 10:sup:`4`

Pattern

Array, Sorting

Solution

The key step is to sort intervals by their start point. We start merging intervals from left to right. Add the first interval to merged_intervals. Suppose we have 2 sorted intervals \([a, b]\) in merged_intervals and and \([c, d]\) in intervals. We only need to check that \(c > b\) to merge the intervals to obtain \([a, \\max(b, d)]\). Moreover, we only need to check the next interval in intervals against the rightmost merged interval. This is because the merged intervals are all disjoint and sorted from left to right.

Code

from __future__ import annotations

from typing import List


def merge(intervals: List[List[int]]) -> List[List[int]]:
    """Merge overlapping intervals.
    """
    intervals = sorted(intervals, key=lambda interval: interval[0])
    merged_intervals = [intervals[0]]

    for interval in intervals[1:]:
        [a, b] = merged_intervals[-1]
        [c, d] = interval

        if c <= b:
            merged_intervals[-1][1] = max(b, d)
        else:
            merged_intervals.append(interval)

    return merged_intervals

Test

>>> from merge_intervals__approach_1 import merge
>>> merge([[1, 3], [2, 6], [8, 10], [15, 18]])
[[1, 6], [8, 10], [15, 18]]
>>> merge([[1, 4], [4, 5]])
[[1, 5]]

Complexity

\(n\) is the number of intervals
Time: \(O(n \log n)\) — sort then merge intervals
Auxiliary Space: \(O(1)\)

merge_intervals__approach_1.merge(intervals: List[List[int]]) → List[List[int]]: Merge overlapping intervals.