Merge Intervals

The problem description can be found in LeetCode.

Approach

This is a classic Interval problem.

Before merging the intervals, we need to sort them to avoid to check all possible pairs, which would require $O(n^2)$ time.

Once sorted, we can iterate over the intervals and either add them to the result list or merge overlapping ones.

intervals = [
    [0, 1],
    [2, 3],
    [4, 5],
]

Here, there is no interval overlap, so we can simply add all of them in the result list.

intervals = [
    [0, 1],
    [2, 3],
    [2, 5],
    [2, 15],
]

Here, the first two do not overlap. So, we could add both of them in the result list. However, the third one overlaps with.

How could we merge them?

Well, the lower bound cannot be smaller then 2, since the intervals are sorted. This means that the first value is always the same.

Regarding the second one, we need to be careful about an edge case, which would consist of something like:

intervals = [
    [0, 10],
    [5, 8],
]

The second value would be picked from the first interval and not from the second one. In fact, the intervals are sorted only by the first value, so we cannot make assumptions about the second one. For it, we have to consider the maximum between the one in the result list and the current interval.

Solution

from typing import List


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

        ans: List[List[int]] = []
        for interval in intervals:
            if not ans or not self.overlap(interval, ans[-1]):
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])

        return ans

    def overlap(self, interval_0, interval_1):
        a, b = interval_0
        c, d = interval_1

        return b >= c and d >= a

Complexity

• Time: $O(nlog(n))$
• Space: $O(n)$

Where $n$ is the size of the intervals list.