MediumLeetCode #56Intervals

Merge Intervals

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

Constraints

1 <= intervals.length <= 10^4, intervals[i].length == 2

Examples

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Solution

Approach

Sort by start time. Iterate and merge if current overlaps with previous (start <= prev end). Otherwise start new interval.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Complexity

Time:O(n log n)

Space:O(n)

Hints

1.Sort intervals by start time
2.Two intervals overlap if second starts before first ends
3.Merge by extending end time

Asked at

Google