Merge intervals

Scenario

You have a list of times when your servers were down. Some downtimes overlap because multiple alerts fired simultaneously.

How do you calculate the actual contiguous blocks of time your system was offline?

Why it exists

Problem: Given an array of intervals, merge all overlapping intervals to produce a list of mutually exclusive intervals that cover all the input.

Naive approach: Compare every interval with every other interval to check for overlaps, merging them and restarting the check until no overlaps remain. This takes `O(n^2)` or worse.

Better idea: Sort the intervals first. Once sorted, overlapping intervals will be adjacent, allowing us to merge them in a single `O(n)` scan.

Mental model

If you line up all the intervals by when they start, you can just walk down the line, stretching out your current block as long as the next piece touches or overlaps it.

Sort the array by start times. Keep a 'current merged interval'. If the next interval in the sorted list overlaps the current one, extend the current one's end time. If it doesn't overlap, save the current interval and start a new one.

Repeated decision: Does this next interval (sorted by start time) overlap the one I'm currently building -- if so, extend it; if not, close it and start a new one.

Explanation

Merge Intervals has a different goal than Interval Scheduling. We aren't trying to pick a subset; we are COALESCING overlapping intervals into their union.

Because the goal is different, the sorting key is different. We MUST sort by START TIME, not end time -- the exact opposite key from Interval Scheduling, which sorts by end time because it is selecting a maximum-count subset rather than coalescing. If you sort by start time, any intervals that overlap are guaranteed to be adjacent in the sorted array.

The algorithm sweeps exactly once. We maintain the `current` interval. When we look at the `next` interval:

1. If `next.start <= current.end`, they overlap. We extend the current interval by taking the maximum of their end times: `current.end = max(current.end, next.end)`. We use `max()` because the `next` interval might be completely swallowed by the `current` one (e.g., merging `[1, 10]` with `[2, 5]`).

2. If `next.start > current.end`, they do not overlap. We push the `current` interval to our results array, and set `current = next` to start building a new contiguous block.

Let's hand-trace with intervals: `[1, 3]`, `[2, 6]`, `[8, 10]`, `[15, 18]`, `[2, 4]`.

1. Sort by start time: `[1, 3]`, `[2, 4]`, `[2, 6]`, `[8, 10]`, `[15, 18]`.

2. Initialize `current` as `[1, 3]`.

3. Next is `[2, 4]`. Start `2 <= 3` (overlap). `current.end = max(3, 4) = 4`. `current` is now `[1, 4]`.

4. Next is `[2, 6]`. Start `2 <= 4` (overlap). `current.end = max(4, 6) = 6`. `current` is now `[1, 6]`. (Notice the triple-overlap resolved perfectly).

5. Next is `[8, 10]`. Start `8 > 6` (no overlap). Push `[1, 6]` to results. `current` becomes `[8, 10]`.

6. Next is `[15, 18]`. Start `15 > 10` (no overlap). Push `[8, 10]` to results. `current` becomes `[15, 18]`.

7. End of array. Push final `current` `[15, 18]` to results.

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

The time complexity is `O(n log n)` due to the sorting step. The linear scan takes `O(n)`. The space complexity is `O(n)` for the output array (or `O(1)` or `O(n)` for sorting depending on the language).

Key points

Sort by start time: Unlike interval scheduling, you must sort by start time to guarantee overlapping intervals are adjacent.
Use max() when extending: When extending an interval, always use `max(current.end, next.end)`. This handles intervals that are completely contained within the current one.
Push the final interval: Don't forget to push the last `current` interval to the results array after the loop finishes.

Pattern: Line Sweep / Sorting

Recognition cues:

The problem asks you to combine or merge overlapping blocks of time or ranges.
You need to find continuous segments.

Failure signals

Sorting by end time instead of start time (conflating with interval scheduling).
Forgetting that one interval might be completely inside another and just blindly doing `current.end = next.end`.
Forgetting to push the very last interval after the loop terminates.

Engineering examples

IP/CIDR Aggregation

Firewalls often receive massive lists of blocked IP ranges that overlap.

Merging the intervals reduces the rule list to a minimal set of non-overlapping IP blocks, speeding up packet filtering.

Calendar Free/Busy Calculation

Finding a time when everyone in a team is free for a meeting.

By taking all busy events for all users and merging them, you get the combined busy time. The gaps between are the free times.

When not to use

You need to find the point in time with the maximum overlapping intervals.: While sorting by start time helps, you usually want a different pattern (sweeping line with +1 for start and -1 for end) to count simultaneous events rather than just merging them.

Common mistakes

Conflating with interval scheduling: If you sort by end time, `[1, 10]` and `[2, 3]` will be ordered `[2, 3]`, `[1, 10]`. Merging them properly becomes much harder because the starts are out of order.
Forgetting `max()` during extension: If `current` is `[1, 10]` and `next` is `[2, 3]`, they overlap. If you just set `current.end = next.end`, you shrink the interval to `[1, 3]`, which is wrong. You need `max(10, 3)`.

Glossary

Union: The combination of two overlapping or touching intervals into a single continuous interval.

Recall questions

Which property should you sort intervals by when solving the Merge Intervals problem?
When two intervals overlap, how do you determine the end time of the merged interval?
What is the time complexity of the standard Merge Intervals solution?

Questions & answers

Given an array of intervals, return an array of non-overlapping intervals that cover all the intervals in the input.

Sort by start time. Initialize a result array with the first interval. Iterate through the rest. If the current interval overlaps the last one in the result array, update the result array's last interval end time using `max()`. Otherwise, push the current interval.

Approach: This is the classic implementation of Merge Intervals. Sorting is the critical enabler.

Given a list of intervals representing the busy times of users, find the first available free slot of a given duration.

Merge all the busy intervals across all users using the standard Merge Intervals algorithm. Then iterate through the merged intervals; the gaps between `merged[i].end` and `merged[i+1].start` are the free slots. Check if any gap is >= the requested duration.

Approach: Merging the intervals collapses the complexity of multiple users into a single timeline, making it trivial to find the gaps.

Interesting facts

This algorithm is functionally a 1-dimensional bounding box calculation, a concept heavily used in graphics programming and collision detection.

Continue learning

Previous: Interval scheduling

Related: Interval scheduling

Return to DSA Roadmap