Merge Intervals

Merge Intervals is the question that teaches you the whole interval pattern. You get a messy pile of time ranges. Some of them overlap. Your job is to squash the overlapping ones into clean single blocks. Once you see the trick here, every other interval question feels easier.

🎯 The Problem

You get a messy list of time blocks and join the overlapping ones.

• An interval is a pair: a start and an end. Think of it as a busy block of time.
• The list is not sorted and some blocks overlap.
• Return a new list where every set of overlapping blocks is joined into one.
• Two blocks overlap when they share even a single point.
• A joined block runs from the smaller start to the larger end.

Input:  intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: [1, 3] and [2, 6] overlap, so they merge into [1, 6].
The other blocks do not overlap anyone, so they stay.

Here is the input drawn on a number line. You can see [1, 3] and [2, 6] cross over each other, so they join into [1, 6].

You can return the answer in any order, but sorted by start is the natural one.

🐢 Approach 1: Repeated Pair Merge (Brute Force)

Merge any overlapping pair, then start the whole scan over.

The idea:

• Compare every block with every other block.
• If two overlap, merge them into one.
• Restart the comparison and repeat until no two overlap.

Why it is weak:

• You restart after every merge, so the same checks run again and again.
• The work drifts to O(n²) or worse.
• Removing and merging blocks mid-loop is fiddly and error prone.

Here is the repeated-pair-merge code:

def merge(intervals):
    changed = True
    while changed:
        changed = False
        result = []
        used = [False] * len(intervals)
        for i in range(len(intervals)):
            if used[i]:
                continue
            cur = intervals[i]
            for j in range(i + 1, len(intervals)):
                if not used[j] and max(cur[0], intervals[j][0]) <= min(cur[1], intervals[j][1]):
                    cur = [min(cur[0], intervals[j][0]), max(cur[1], intervals[j][1])]
                    used[j] = True
                    changed = True
            result.append(cur)
        intervals = result
    return intervals

⚡ Approach 2: Sort Then Sweep (Best)

The idea in one line: sort by start, then overlaps sit next to each other, so one pass merges them.

The idea:

• Sort the blocks by their start.
• After sorting, any overlapping blocks are neighbors.
• Keep one current merged block and compare each next block to it.

How it works:

• Move left to right through the sorted list.
• Ask: does this block start before the current block ends?
• If yes, they overlap, so stretch the current end to the larger of the two ends.
• If no, there is a gap, so save the current block and start a new current.

Why it is fast:

• Sorting costs O(n log n). The sweep after it is one pass, O(n).
• The sort is the heavy part, so the total is O(n log n).

Here is the sweep as a decision flow for each block after sorting.

Steps to Solve

1. Sort the intervals by their start value.
2. Put the first interval into the result as the current block.
3. Walk through the rest. For each block, compare its start with the current block’s end.
4. If the start is not past the current end, they overlap, so push the current end to the larger end.
5. If there is a gap, add the current block to the result and make this block the new current.
6. After the loop, the last current block is already in the result. Return the result.

#include <stdio.h>
#include <stdlib.h>

// compare by start for qsort
int cmp(const void *a, const void *b) {
    int *x = *(int **)a;
    int *y = *(int **)b;
    return x[0] - y[0];
}

int main(void) {
    int raw[][2] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    int n = 4;

    int *arr[4];
    for (int i = 0; i < n; i++) arr[i] = raw[i];

    qsort(arr, n, sizeof(int *), cmp);  // sort by start

    int result[4][2];
    int count = 0;
    result[count][0] = arr[0][0];
    result[count][1] = arr[0][1];

    for (int i = 1; i < n; i++) {
        if (arr[i][0] <= result[count][1]) {        // overlap
            if (arr[i][1] > result[count][1])
                result[count][1] = arr[i][1];        // stretch end
        } else {
            count++;                                 // gap, new block
            result[count][0] = arr[i][0];
            result[count][1] = arr[i][1];
        }
    }
    count++;

    printf("[");
    for (int k = 0; k < count; k++) {
        printf("[%d, %d]", result[k][0], result[k][1]);
        if (k < count - 1) printf(", ");
    }
    printf("]\n");
    return 0;
}

[[1, 6], [8, 10], [15, 18]]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());  // sort by start
    vector<vector<int>> result;
    result.push_back(intervals[0]);

    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] <= result.back()[1]) {           // overlap
            result.back()[1] = max(result.back()[1], intervals[i][1]);
        } else {
            result.push_back(intervals[i]);                  // gap
        }
    }
    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    vector<vector<int>> result = merge(intervals);

    cout << "[";
    for (int k = 0; k < (int)result.size(); k++) {
        cout << "[" << result[k][0] << ", " << result[k][1] << "]";
        if (k < (int)result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[[1, 6], [8, 10], [15, 18]]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // sort by start
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = result.get(result.size() - 1);
            if (intervals[i][0] <= last[1]) {                 // overlap
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                result.add(intervals[i]);                     // gap
            }
        }
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] result = merge(intervals);

        StringBuilder sb = new StringBuilder("[");
        for (int k = 0; k < result.length; k++) {
            sb.append("[").append(result[k][0]).append(", ").append(result[k][1]).append("]");
            if (k < result.length - 1) sb.append(", ");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

[[1, 6], [8, 10], [15, 18]]

def merge(intervals):
    intervals.sort(key=lambda block: block[0])  # sort by start
    result = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = result[-1][1]
        if start <= last_end:                  # overlap with last block
            result[-1][1] = max(last_end, end)
        else:
            result.append([start, end])        # gap, add new block
    return result


intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge(intervals))

[[1, 6], [8, 10], [15, 18]]

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]); // sort by start
  const result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    if (intervals[i][0] <= last[1]) {            // overlap
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      result.push(intervals[i]);                 // gap
    }
  }
  return result;
}

const intervals = [[1, 3], [2, 6], [8, 10], [15, 18]];
console.log(JSON.stringify(merge(intervals)));

[[1,6],[8,10],[15,18]]

Now let us walk through the Python version line by line and see why each part is written this way.

def merge(intervals):
    intervals.sort(key=lambda block: block[0])
    result = [intervals[0]]

We sort by block[0], which is the start of each block. This is the whole trick. After sorting, overlaps sit next to each other. We seed result with the first block so we always have a current block to compare against.

    for start, end in intervals[1:]:
        last_end = result[-1][1]

We loop from the second block onward. result[-1] is the last block we added, which is our current merged block. We read its end into last_end because we compare the new start against it.

        if start <= last_end:
            result[-1][1] = max(last_end, end)

The check start <= last_end reads as “this block starts before the current one ends.” That means they overlap. So we stretch the current block by setting its end to the larger of the two ends. We use max because the new block might end earlier than the current one, and we must not shrink it.

        else:
            result.append([start, end])
    return result

If the start is past last_end, there is a gap. The blocks do not touch. So we close the current block and add this one as the new current. After the loop the last current block is already inside result, so we just return it.

⏱️ Time and Space Complexity

The brute force keeps restarting its comparisons, so it drifts to O(n²) or worse. The sort then sweep costs O(n log n) for the sort plus O(n) for the single pass. The sort dominates, so the total is O(n log n). Space is O(n) for the answer, plus whatever the sort uses. So the big idea is that sorting once buys you a clean linear sweep after it.

🧩 Key Takeaways

• ✅ Sorting by start puts every overlap right next to its neighbor.
• ✅ Keep one current merged block and compare each new block to it.
• ✅ Two blocks overlap when the new start is not past the current end.
• ✅ When they overlap, push the end to the larger end with max.
• ✅ The sort is the expensive part, so the total time is O(n log n).

🚀 What’s Next?

• Insert Interval
• Non-overlapping Intervals