Merge Intervals

MediumGoogleAmazonMetaMicrosoftBloomberg

Problem

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping result.

Intuition — the key insight

If we sort by start time, overlapping intervals are guaranteed to be adjacent. Then a single sweep suffices: maintain a 'current' interval and extend its end if the next interval overlaps, otherwise push current and move to next.

Approach

1. Sort by start time

Sort intervals by their start value. This guarantees any interval that could overlap with the current one comes immediately after it.

2. Single sweep merge

Initialize result with the first interval. For each subsequent interval: if its start ≤ result's last end, they overlap — extend the end to max(current end, next end). Otherwise push result's last and start fresh with next interval.

Complexity

Time

O(n log n)

Space

O(n)

Sorting dominates at O(n log n). The sweep is O(n). Output array is O(n) in the worst case (no overlaps).

Solution code

Python

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        
        if start <= last_end:
            # Overlapping — extend the end
            merged[-1][1] = max(last_end, end)
        else:
            # No overlap — start new interval
            merged.append([start, end])
    
    return merged

Edge cases to remember

⚠Single interval: return as-is

⚠All intervals overlap: return one merged interval

⚠Touching intervals [1,3] and [3,5]: start(3) <= end(3) so they merge to [1,5]

⚠Interval completely inside another: [1,10] and [2,5] → [1,10]

Hints

What pattern do you think this problem uses?