Merge Intervals

Explanation & Solution

Description

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

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

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

Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4

Approach

Intervals pattern

1. Sort by Start Time

Sort the intervals array by each interval's start value in ascending order
This guarantees that if two intervals overlap, they will be adjacent (or near each other) in the sorted order

2. Initialize the Merged List

Create a merged array and add the first sorted interval to it
This serves as the starting point for comparisons

3. Iterate and Compare

For each subsequent interval curr, look at the last interval in the merged array
Compare curr[0] (current start) with last[1] (last merged end)

4. Merge or Append

If overlapping (curr[0] <= last[1]): extend the last merged interval's end to Math.max(last[1], curr[1])
If not overlapping (curr[0] > last[1]): push curr as a new separate interval into merged

5. Return Result

After processing all intervals, merged contains all non-overlapping intervals that cover every original interval

Key Insight

Sorting by start time is the critical first step — it reduces the problem to a single linear scan
After sorting, you only need to check whether the current interval overlaps with the most recently merged interval
The overall complexity is O(n log n) due to sorting, with O(n) space for the output

Visualization

Input:

Interval Timeline[[1,3], [2,6], [8,10], [15,18]]

—

Press play to start visualization

CurrentCompareOverlapMerged

9 steps

Solution Code

Insert Interval