Intervals: merge & insert

How does Intervals: merge & insert work?

Sort the intervals by their start value. Nothing below works without that order.

Take the first interval as the current block. Everything after it is compared against this block.

Look at the next interval and read its start. Compare that start against the current end.

If the start is not past the current end, the two touch. Widen the current end to the larger of the two.

If the start is past it, the block is finished. Push it and make the new interval current.

One pass covers the whole list. The last block is pushed after the loop ends.

1. current = [1, 3]The list is sorted by start. The first interval opens a block.
2. next = [2, 6]2 is not past 3, so they overlap. The end grows to 6.
3. current = [1, 6], next = [8, 10]8 is past 6. The block is finished and pushed.
4. current = [8, 10], next = [9, 12]9 is not past 10. The end grows to 12.
5. [[1, 6], [8, 12]]The last block is pushed after the loop. Four intervals became two.

function mergeIntervals(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const result = [];
    for (const [start, end] of intervals) {
        const last = result[result.length - 1];
        if (last && start <= last[1]) {
            last[1] = Math.max(last[1], end);
        } else {
            result.push([start, end]);
        }
    }
    return result;
}

A worked example of Intervals: merge & insert

Insert one interval into a sorted list

You get a sorted list of intervals that do not overlap, plus one new interval.

Insert it, merge whatever it touches, and keep the result sorted and disjoint.

Copy across every interval that ends before the new one starts.

Then absorb every interval that overlaps, widening the new one. Copy the remaining tail unchanged.

function insert(intervals, newInterval) {
    const result = [];
    let [start, end] = newInterval;
    let i = 0;

    while (i < intervals.length && intervals[i][1] < start) {
        result.push(intervals[i]); // ends before the new one begins
        i++;
    }

    while (i < intervals.length && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]); // the later interval may end sooner
        i++;
    }
    result.push([start, end]);

    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

When should you use Intervals: merge & insert?

These phrases in a problem statement point here:

• •merge overlapping intervals
• •insert a new interval into a sorted list
• •meetings, bookings, or ranges that overlap
• •given as [start, end] pairs
• •free time / busy time between intervals

What is Intervals: merge & insert confused with?

• Sweep line (event counting): A sweep breaks each interval into two events and counts. Merging keeps the intervals whole.
• Greedy (exchange argument): Removing the fewest intervals is a greedy choice by end time. Merging only joins what overlaps.
• Sort with a custom comparator: The sort by start is the setup step. This page is about the pass that follows it.
• Difference array: That counts how deep the overlap runs at each index. Merging returns intervals, not counts.

Common mistakes with Intervals: merge & insert

• Skipping the sort

  The single pass assumes the starts only grow. Unsorted input merges the wrong pairs.

• Guessing the overlap comparison

  Whether [1, 2] and [2, 3] touch is the problem's choice. Read the statement before picking the operator.

• Forgetting the final block

  The current interval is pushed only after the loop. Without that the answer loses one.

• Taking the end from the later interval

  A later interval can end sooner than the current one. The new end is the maximum of both.

Which interview problems use Intervals: merge & insert?

• Merge intervals: The plain form: sort by start, then one pass.
• Insert interval: The list is already sorted, so only the middle needs merging.
• Non-overlapping intervals: Keep the interval that finishes first, greedily.
• Meeting rooms: Any overlap at all makes the answer false.
• Interval list intersections: Two sorted lists walked with two pointers.
• Employee free time: Merge every busy block, then read the gaps between.
• Remove covered intervals: Sort by start, and on a tie put the longer one first.

What is the time and space complexity of Intervals: merge & insert?

O(n log n)

n up to 1e6 costs O(n log n), all of it in the sort. The pass afterwards is O(n).