Merge Intervals

Problem Statement

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.

You may return the answer in any order.

Note: Intervals are non-overlapping if they have no common point. For example, [1, 2] and [3, 4] are non-overlapping, but [1, 2] and [2, 3] are overlapping.

Example 1:

Input: intervals = [[1,3],[1,5],[6,7]]
Output: [[1,5],[6,7]]

Example 2:

Input: intervals = [[1,2],[2,3]]
Output: [[1,3]]

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• 0 <= start <= end <= 1000

Recommended Time and Space Complexity

Aim for O(n log n) time complexity due to sorting, and O(1) or O(n) space complexity depending on the sorting algorithm implementation.

Hint 1

Sort the intervals based on their start times.

Hint 2

Iterate through the sorted intervals, merging overlapping intervals as you go.

Hint 3

Keep track of the merged intervals in a result list.

Solution

Sorting

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda pair: pair[0])
    output = [intervals[0]]

    for start, end in intervals:
        last_end = output[-1][1]

        if start <= last_end:
            output[-1][1] = max(last_end, end)
        else:
            output.append([start, end])
    return output

Time complexity: O(n log n) Space complexity: O(1) or O(n) depending on sorting algorithm implementation.