---
title: "Intervals: merge & insert"
url: https://algopath.pro/patterns/intervals-merge
language: en
summary: "Sort the intervals by start, then walk them once. Two neighbours merge whenever the next start is not past the current end."
updated: 2026-08-24
---

# Intervals: merge & insert

Sort the intervals by start, then walk them once. Two neighbours merge whenever the next start is not past the current end.

## 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.

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

## When should you use Intervals: merge & insert?

- 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.

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

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

## 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.

```javascript
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;
}
```

## 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.

## JavaScript

```javascript
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;
}
```

## Python

```python
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    result = []
    for start, end in intervals:
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result
```

## PHP

```php
function mergeIntervals(array $intervals): array {
    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]);
    $result = [];
    foreach ($intervals as [$start, $end]) {
        $lastIdx = count($result) - 1;
        if ($lastIdx >= 0 && $start <= $result[$lastIdx][1]) {
            $result[$lastIdx][1] = max($result[$lastIdx][1], $end);
        } else {
            $result[] = [$start, $end];
        }
    }
    return $result;
}
```