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

Approaches

Explanation

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


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__sorting 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

Measure

Complexity

Notes

Time

\(O(n \log n)\)

sort then merge intervals

Auxiliary Space

\(O(1)\)
merge_intervals__sorting.merge(intervals: list[list[int]]) → list[list[int]]

Merge overlapping intervals.