Merge Intervals

MediumgreedyGoogleAmazon

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals.

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

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

Hint 1

Sort intervals by their start times first.

Official asymptotic Big-O runtime and auxiliary memory analysis

Linearithmic

Algorithmic Approach

Sort intervals by start time. Iterate through them, merging overlapping intervals into the current interval or starting a new interval.

Time ComplexityO(N log N)

Why:

Sorting intervals by start time takes O(N log N), followed by a single linear O(N) sweep to merge overlapping pairs.

Space ComplexityO(1)

Why:

The merged intervals list stores up to N non-overlapping output intervals.

Big-O Growth CurveLinearithmic (O(N log N))

Scales efficiently for sorting and divide-and-conquer algorithms.

🔍 Dry Run

Solution⏱ O(N log N) | 💾 O(1)

[1, 3]

[2, 6]

[8, 10]

[15, 18]

-1