Merging Overlapping Intervals

Hello! In our last lesson, we explored how to validate or refute a greedy strategy using counterexamples and exchange arguments. We saw that for the Fractional Knapsack problem, the greedy choice of taking the item with the highest value density first is optimal, largely because sorting by that metric creates a sequence of safe, locally-optimal decisions.

Today, we'll apply this powerful combination of sorting and greedy thinking to a new category of problems: those involving intervals. We'll tackle the "Merge Intervals" problem, a common interview question that serves as a foundation for many others. You'll see how arranging the input in a specific order transforms a complex problem into a straightforward linear scan, reinforcing the patterns we've begun to build.

By the end of this lesson, you will be able to devise and implement an efficient algorithm to merge a collection of overlapping intervals by first sorting them by their start times.

The "Merge Intervals" Problem

Imagine you have a list of time slots for meetings, represented as pairs of start and end times. Some of these meetings might overlap. Your task is to condense this list into the minimum number of non-overlapping intervals that cover all the original time slots.

For example, given the intervals [[1, 3], [2, 6], [8, 10], [15, 18]], the intervals [1, 3] and [2, 6] overlap. They can be merged to form a single interval, [1, 6]. The other intervals, [8, 10] and [15, 18], do not overlap with any others, so they remain as they are. The final merged list would be [[1, 6], [8, 10], [15, 18]].

An important detail is that intervals that "touch" at their endpoints are considered overlapping. For instance, [1, 4] and [4, 5] would merge into [1, 5].

The Greedy Strategy: Sort and Scan

If the intervals are in a random order, figuring out all the overlaps seems complicated. You might have to compare every interval with every other interval, which would be inefficient, likely taking $O(n^2)$ time. As you know from your development experience, nested loops over the same large collection are often a performance red flag.

This is where a greedy approach, enabled by sorting, comes in. What if we first sort the intervals based on their start times?

Once sorted, a crucial property emerges: if two intervals are going to overlap, they will be adjacent in the sorted list. This insight simplifies the problem dramatically. We no longer need to look at all possible pairs. We can simply iterate through the sorted intervals and make a local decision at each step: does the current interval overlap with the previous one?

This is a "greedy" approach because at each step, we greedily extend our current merged interval as far as possible. This choice is "safe" because, thanks to sorting, once we encounter an interval that doesn't overlap with our current merged block, no subsequent interval can either (since all subsequent intervals will start even later).

The following resource provides an excellent explanation of this core idea.

The videos below offer great visual walkthroughs of this concept, plotting the intervals on a number line to make the effect of sorting intuitive.

The Algorithm Step-by-Step

With the core idea in place, let's define the algorithm. The process is a single pass through the sorted intervals while maintaining the "current" merged interval.

1. Sort: Sort the array of intervals in ascending order based on their start times.
2. Initialize: Create a result list for the merged intervals. Take the first sorted interval and consider it the current_merge.
3. Iterate and Merge: Loop through the remaining sorted intervals, one by one. For each next_interval:
   • Check for Overlap: Compare the start of next_interval with the end of current_merge. An overlap exists if next_interval.start <= current_merge.end.
   • If Overlap: Greedily extend the current_merge by updating its end point: current_merge.end = max(current_merge.end, next_interval.end). We use max to handle cases where one interval is completely contained within another (e.g., merging [1, 10] and [2, 5] should result in [1, 10]).
   • If No Overlap: The current_merge is complete. Add it to the result list. Then, the next_interval becomes the new current_merge.
4. Finalize: After the loop finishes, the last current_merge has not yet been added to the result list. Make sure to add it.

Let's trace this with an example: [[1,3], [2,6], [8,10], [15,18]]. The input is already sorted.

• Step 1: Initialize merged_intervals = []. current_merge starts as [1, 3].
• Step 2: Look at the next interval, [2, 6].
  • Does it overlap with [1, 3]? Yes, because 2 <= 3.
  • Merge them: The new current_merge becomes [1, max(3, 6)], which is [1, 6].
• Step 3: Look at the next interval, [8, 10].
  • Does it overlap with [1, 6]? No, because 8 > 6.
  • The [1, 6] merge is complete. Add [1, 6] to merged_intervals.
  • [8, 10] becomes the new current_merge.
• Step 4: Look at the next interval, [15, 18].
  • Does it overlap with [8, 10]? No, because 15 > 10.
  • The [8, 10] merge is complete. Add [8, 10] to merged_intervals.
  • [15, 18] becomes the new current_merge.
• Step 5: The loop is done. Add the last current_merge, [15, 18], to merged_intervals.

Final Result: [[1, 6], [8, 10], [15, 18]].

The following resource provides a detailed text walkthrough of this algorithm.

Implementation in TypeScript

Now, let's translate this logic into code. Given your background in front-end development, the syntax should feel familiar. The key parts are the custom sort comparator and the loop that performs the merge.

function merge(intervals: number[][]): number[][] {
    // Handle edge case of empty or single interval
    if (intervals.length <= 1) {
        return intervals;
    }

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

    const mergedIntervals: number[][] = [];
    let currentStart = intervals[0][0];
    let currentEnd = intervals[0][1];

    // 2. Iterate through the rest of the intervals
    for (let i = 1; i < intervals.length; i++) {
        const intervalStart = intervals[i][0];
        const intervalEnd = intervals[i][1];

        // 3. Check for overlap
        if (intervalStart <= currentEnd) {
            // Overlap exists, extend the current merge
            currentEnd = Math.max(currentEnd, intervalEnd);
        } else {
            // No overlap, push the completed interval and start a new one
            mergedIntervals.push([currentStart, currentEnd]);
            currentStart = intervalStart;
            currentEnd = intervalEnd;
        }
    }

    // 4. Add the last merged interval
    mergedIntervals.push([currentStart, currentEnd]);

    return mergedIntervals;
}

Complexity Analysis

• Time Complexity: $O(n\log n)$. The intervals.sort() operation dominates the runtime. The single loop for merging takes $O(n)$ time, which is overshadowed by the sort.
• Space Complexity: This can be described in two ways. The auxiliary space required by the algorithm (e.g., for sorting) is typically $O(\log n)$ or $O(n)$ depending on the sort implementation. In JavaScript, Array.prototype.sort() can use up to $O(n)$ space. However, we also need space for the output array, which can be up to $O(n)$ in the worst case (if no intervals merge). In an interview, it's good practice to state both: $O(n)$ for the output and note the additional space for sorting.

For a final review of the implementation and common errors, the following resources are very helpful.

Conclusion

In this lesson, we dissected the "Merge Intervals" problem and saw how a greedy strategy, unlocked by sorting, provides an elegant and efficient solution. This pattern of sort -> iterate -> decide is a fundamental tool in your algorithmic toolbox, especially for problems involving intervals or ordered data.

Here are the key takeaways:

• Problem Transformation: Sorting by start time simplifies the problem from comparing all pairs to making a simple local check between adjacent intervals.
• Greedy Choice: The safe, greedy choice at each step is to extend the current merged interval if an overlap exists. If not, we finalize the current merge and start a new one.
• Implementation Details: Key implementation points include handling the sort, the overlap condition (<=), updating the end boundary using max(), and remembering to add the final interval after the loop.

In our next lesson, we'll continue with interval problems by looking at how to select the maximum number of non-overlapping activities from a set. This will introduce a variation on today's theme, where we'll find that sorting by the end time is the key to another correct greedy strategy.