Merge Intervals

Concept

An Interval is an array of two numbers representing a start and an end boundary (e.g., [1, 5]). It usually represents timeframes, meetings, or geographic coordinates.

The Merge Intervals pattern asks you to take a messy list of intervals and combine any that overlap.
For example, if Alice has a meeting from 1:00 to 4:00 ([1, 4]), and Bob has a meeting from 3:00 to 5:00 ([3, 5]), the room is booked continuously from 1:00 to 5:00 ([1, 5]).

The Golden Rule: Sort First

You absolutely cannot solve an interval problem efficiently if the intervals are in random order.
The very first step of almost every interval problem is sorting the array based on the start times. ($O(N \log N)$ time).

Once sorted, you can iterate through the list linearly ($O(N)$ time). Because they are sorted by start time, you only ever need to compare the current interval against the very last interval you processed.

Mental Model

Sorted Intervals: [[1, 3], [2, 6], [8, 10], [15, 18]]

1. Push the first interval into a result array: result = [[1, 3]].
2. Look at the next interval: [2, 6].
3. Compare the start of the new interval (2) with the end of the last interval in our result (3).
4. Because 2 <= 3, they overlap!
5. Merge them: Update the end of the last interval in our result to be the Math.max(3, 6). result is now [[1, 6]].
6. Look at the next interval: [8, 10].
7. 8 is greater than 6. They don’t overlap. Just push it into the result. result is now [[1, 6], [8, 10]].

Implementation

// Time Complexity: O(N log N) due to the sorting step
// Space Complexity: O(N) to hold the output array
function mergeIntervals(intervals: number[][]): number[][] {
    if (intervals.length === 0) return [];

    // 1. Sort by the start time
    intervals.sort((a, b) => a[0] - b[0]);

    const result: number[][] = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const current = intervals[i];
        const lastMerged = result[result.length - 1];

        // Do they overlap?
        if (current[0] <= lastMerged[1]) {
            // Yes! Extend the end boundary of the last merged interval
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // No! It's a completely separate interval. Push it.
            result.push(current);
        }
    }

    return result;
}

Insert Interval

A very common variation (LeetCode #57) provides a pre-sorted list of non-overlapping intervals, and asks you to insert a single new interval into the correct spot, merging if necessary.
Because the array is already sorted, you do not need to call .sort(). You can solve it in strict $O(N)$ time.

1. Left Phase: Push all intervals that end before the new interval starts.
2. Merge Phase: For all intervals that overlap the new interval, continuously mutate the new interval (newInterval[0] = Math.min(...), newInterval[1] = Math.max(...)). Push the mutated interval once.
3. Right Phase: Push all remaining intervals.

Interview Questions

Q: In the mergeIntervals function, why do we use Math.max(lastMerged[1], current[1]) instead of just setting lastMerged[1] = current[1]?
A: We use Math.max to handle Complete Submersion (Envelopment).
Imagine the intervals [[1, 10], [2, 5]].
They overlap, because 2 <= 10. But if we just blindly took the end of the second interval (5), the merged result would become [1, 5], which is wrong! The first interval actually completely swallowed the second one. By using Math.max(10, 5), the merged result correctly remains [1, 10].

Q: A problem asks: “Given an array of meeting time intervals, return the minimum number of conference rooms required.” How is this different from merging?
A: This is the “Meeting Rooms II” problem. Merging tells you the total continuous block of time booked. It doesn’t tell you how many parallel rooms you need.
To solve for parallel rooms, you must track overlapping intervals dynamically. The most common solution is the Two Pointer (Chronological Ordering) approach: you split the start times and end times into two separate sorted arrays. As you iterate through time, if a meeting starts before the previous one ends, you increment a roomsRequired counter. If a meeting ends, you decrement the counter.
Alternatively, you can use a Min-Heap to track the earliest ending meeting currently occupying a room.