Merge Intervals

This function merges all overlapping intervals from a given list of intervals.

Problem Description

Given a list of intervals where each interval is represented as [start, end], merge all overlapping intervals and return a list of non-overlapping intervals that cover the same ranges.

Example

Input

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

Output

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

Approach

Handle edge case: If the input list is empty, return an empty list.

Sort intervals by their starting values.

Iterate through intervals:

Compare the current interval with the last merged interval.

If they overlap (current_start <= last_end), merge them by extending the end.

Otherwise, add the current interval as a new entry.

Implementation def merge(intervals): if not intervals: return []

# Sort intervals by start time
intervals.sort(key=lambda x: x[0])

merged = [intervals[0]]

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

    # Overlapping intervals → merge
    if start <= last_end:
        merged[-1][1] = max(last_end, end)
    else:
        merged.append([start, end])

return merged

Complexity Analysis

Time Complexity: O(n log n) due to sorting

Space Complexity: O(n) for the merged output list