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 point. Merge overlapping intervals by comparing start with previous end.

Implementation

def merge(intervals):
    if not intervals:
        return []
    
    intervals.sort()
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        if current[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], current[1])
        else:
            merged.append(current)
    
    return merged

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(1)

Key Learning Points

Sort by start timeCompare overlapsTrack merged result