SyntaxPilot
Courses/DSA and Coding Problems/Lesson 20
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 20 of 90

Merge intervals

queued

These are the notes for DSA episode 20. Right after the sorting block (episodes 16 to 19), this is the problem that shows why sorting matters in interviews: merge intervals. The brute force compares every pair of intervals and restarts after every merge, so one lakh bookings hit the time limit. One idea fixes it: sort by start time, and overlapping intervals become neighbours, so a single sweep that compares each interval with the last merged block is enough: O(n log n). We also fix three real bugs and solve the famous follow-up, meeting rooms (how many halls do we need?). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A wedding hall keeps one booking register. Each booking is a start time and an end time: 1-3, 2-6, 8-10, 15-18. Decorators, caterers and the band all write in it, so bookings overlap: 2-6 starts before 1-3 has ended.

The manager doesn't care who booked what. He wants the busy blocks: 1-6, 8-10, 15-18. The free slots are the gaps between them: 6-8 and 10-15. Calendar apps, video-call schedulers and railway platform planners solve exactly this problem.

In the hall In the code
A booking 2-6 An interval {2, 6} (an int[] of length 2)
The register int[][] intervals
Two bookings clash The intervals overlap
A busy block A merged interval
Reading the register in time order Sorting by start

Problem statement

Given an array of intervals intervals[i] = [start, end], merge all overlapping intervals and return the merged, non-overlapping intervals (sorted by start).

Input:  [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
  • Overlap test: intervals a and b overlap when a.start <= b.end && b.start <= a.end. If either part is false, one interval lies completely to the left of the other.
  • Touching counts: [1,4] and [4,5] overlap (they share time 4) and merge into [1,5]. That's why the test uses <=.
  • Merging two overlapping intervals: [min(starts), max(ends)].
  • Edge cases: one interval inside another ([1,10], [2,3]), a single interval, unsorted input, an empty array.

Brute force: merge, restart, repeat

The pen-and-register way: look at every pair (i, j). If they overlap, merge j into i and delete j. A merge makes a block bigger, so it may now reach an interval it didn't touch before, so start the scan again. Stop when a full scan merges nothing.

import java.util.*;

public class Main {
    static int[][] brute(int[][] in) {
        List<int[]> list = new ArrayList<>(Arrays.asList(in));
        boolean changed = true;
        while (changed) {
            changed = false;
            search:
            for (int i = 0; i < list.size(); i++)
                for (int j = i + 1; j < list.size(); j++) {
                    int[] a = list.get(i), b = list.get(j);
                    if (a[0] <= b[1] && b[0] <= a[1]) {
                        a[0] = Math.min(a[0], b[0]);
                        a[1] = Math.max(a[1], b[1]);
                        list.remove(j);
                        changed = true;
                        break search;
                    }
                }
        }
        return list.toArray(new int[0][]);
    }
    static void show(int[][] a) {
        System.out.println(Arrays.deepToString(brute(a)));
    }
    public static void main(String[] args) {
        show(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
    }
}

Output:

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

search: is a label: break search; leaves both loops at once, so the while loop starts a fresh scan.

The big input: one lakh bookings

A booking app for every hall in a city: one lakh bookings, random start times, each up to 500 minutes long.

        int n = 100000;
        int[][] b = new int[n][];
        Random r = new Random(7);
        for (int i = 0; i < n; i++) {
            int s = r.nextInt(100000000);
            b[i] = new int[]{s, s + r.nextInt(500)};
        }
        long t0 = System.nanoTime();
        int[][] m = brute(b);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(n + " -> " + m.length + ", " + ms + " ms");

Result: Time Limit Exceeded (it was still running after 30 seconds on our machine).

Why the brute force is slow

n Pair checks in ONE scan (about n²/2)
1,000 5 lakh: instant
10,000 5 crore
1 lakh 5 × 10⁹, per scan

In an unsorted register, any interval might overlap any other one, anywhere in the list, so we must compare every pair: O(n²) per scan. Every merge throws the scan away and starts again, so with many merges the worst case is O(n³).

The key insight: sort by start

Sort the intervals by start time. Now every interval starts at or after all the ones before it, so the only block it can overlap is the last block we built (nothing earlier ends later than that block, because we always extend it to the biggest end seen so far).

For each interval cur in sorted order:

  • cur.start <= last.end → overlap: last.end = max(last.end, cur.end)
  • otherwise → a gap: cur starts a new block

Trace on the shuffled register [[8,10],[1,3],[15,18],[2,6]]:

Step cur Check Merged blocks
sort → [1,3] [2,6] [8,10] [15,18]
1 [1,3] out is empty [1,3]
2 [2,6] 2 <= 3 → overlap, end = max(3, 6) [1,6]
3 [8,10] 8 > 6 → new block [1,6] [8,10]
4 [15,18] 15 > 10 → new block [1,6] [8,10] [15,18]

The optimal solution in Java

import java.util.*;

public class Main {
    static int[][] merge(int[][] in) {
        Arrays.sort(in, (x, y) -> Integer.compare(x[0], y[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] cur : in) {
            if (out.isEmpty() || out.get(out.size() - 1)[1] < cur[0])
                out.add(cur);
            else {
                int[] last = out.get(out.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            }
        }
        return out.toArray(new int[0][]);
    }
    static void show(int[][] a) {
        System.out.println(Arrays.deepToString(merge(a)));
    }
    public static void main(String[] args) {
        show(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        show(new int[][]{{1, 4}, {4, 5}});
        show(new int[][]{{1, 10}, {2, 3}});
        show(new int[][]{{5, 7}});
        show(new int[][]{{8, 10}, {1, 3}, {2, 6}});
        show(new int[][]{});
    }
}

Output:

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

Example, touching, contained, single, unsorted, empty: all correct. The empty array needs no special case: the loop simply never runs.

On the same one lakh bookings that killed the brute force (int[][] m = merge(b);):

100000 -> 77807, 251 ms

A fraction of a second (the exact milliseconds change from run to run).

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> mergeIntervals(vector<vector<int>> in) {
    sort(in.begin(), in.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[0] < y[0];
    });
    vector<vector<int>> out;
    for (auto& cur : in) {
        if (out.empty() || out.back()[1] < cur[0])
            out.push_back(cur);
        else
            out.back()[1] = max(out.back()[1], cur[1]);
    }
    return out;
}

void show(const vector<vector<int>>& in) {
    auto m = mergeIntervals(in);
    cout << "[";
    for (size_t i = 0; i < m.size(); i++)
        cout << (i ? ", " : "") << "[" << m[i][0] << ", " << m[i][1] << "]";
    cout << "]\n";
}

int main() {
    show({{1, 3}, {2, 6}, {8, 10}, {15, 18}});
    show({{1, 4}, {4, 5}});
    show({{1, 10}, {2, 3}});
    show({{5, 7}});
    show({{8, 10}, {1, 3}, {2, 6}});
    show({});
}

Output:

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

In C++ a comparator returns a bool (x[0] < y[0]), so there is no subtraction to overflow.

The same solution in Python

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for start, end in intervals:
        if not out or out[-1][1] < start:
            out.append([start, end])
        else:
            out[-1][1] = max(out[-1][1], end)
    return out

print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(merge([[1, 4], [4, 5]]))
print(merge([[1, 10], [2, 3]]))
print(merge([[5, 7]]))
print(merge([[8, 10], [1, 3], [2, 6]]))
print(merge([]))

Output:

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

Three real bugs

Bug 1: last[1] = cur[1] instead of the max

                last[1] = cur[1];

On [[1, 10], [2, 3]] it printed:

[[1, 3]]

Wrong: the hall is busy until 10. A contained interval ends earlier than the block, so overwriting the end shrinks it. Always Math.max(last[1], cur[1]).

Bug 2: forgetting to sort

Without the Arrays.sort line, on [[8, 10], [1, 3], [2, 6]] it printed:

[[8, 10]]

[1,3] "overlaps" [8,10] by the check (10 < 1 is false), so it gets swallowed. The last-block check is only correct on sorted input.

Bug 3: the comparator x[0] - y[0] overflows

        Arrays.sort(in, (x, y) -> x[0] - y[0]);
        ...
        int[][] t = {{2000000000, 2000000005},
                {-2000000000, -1999999990}};
        System.out.println(Arrays.deepToString(merge(t)));

Output:

[[2000000000, 2000000005]]

2000000000 - (-2000000000) is 4 × 10⁹, which doesn't fit in an int (max 2,147,483,647). It overflows to a negative number, so the sort puts two billion first, and then the minus-two-billion booking looks like an overlap and is swallowed. Integer.compare(x[0], y[0]) never overflows.

Complexity

Approach Time Extra space 1 lakh bookings
Brute force (every pair, restart after each merge) O(n²) per scan, up to O(n³) O(n) for the list Time Limit Exceeded
Sort + one sweep O(n log n) sort + O(n) sweep = O(n log n) O(n) for the output (+ the sort's own space) 251 ms

Sorting dominates. If the input is already sorted by start, the sweep alone is O(n).

Follow-up: how many halls do we need? (meeting rooms)

Now the owner has many halls and events 9-12, 11-14, 13-16. At 11:30 the first two run together, so at least 2 halls. At 12 the first ends and its hall is free for the third at 13. The answer is the largest number of events running at the same moment: 2.

Sort the start times and the end times separately. Walk through the starts; before each start, every event that has already ended (end <= start) frees a hall.

import java.util.*;

public class Main {
    static int rooms(int[][] in) {
        int n = in.length;
        int[] s = new int[n], e = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = in[i][0];
            e[i] = in[i][1];
        }
        Arrays.sort(s);
        Arrays.sort(e);
        int used = 0, best = 0, j = 0;
        for (int i = 0; i < n; i++) {
            while (e[j] <= s[i]) { j++; used--; }
            used++;
            best = Math.max(best, used);
        }
        return best;
    }
    public static void main(String[] args) {
        int[][] season = {{9, 12}, {11, 14}, {13, 16}};
        int[][] touch = {{9, 12}, {12, 15}};
        int[][] inside = {{1, 10}, {2, 3}, {4, 5}};
        System.out.println(rooms(season));
        System.out.println(rooms(touch));
        System.out.println(rooms(inside));
    }
}

Output:

2
1
2

An event ending at 12 frees the hall for one starting at 12 (<=), so touch needs one hall. O(n log n) time, O(n) space.

C++:

#include <bits/stdc++.h>
using namespace std;

int rooms(const vector<pair<int,int>>& in) {
    vector<int> s, e;
    for (auto [a, b] : in) { s.push_back(a); e.push_back(b); }
    sort(s.begin(), s.end());
    sort(e.begin(), e.end());
    int used = 0, best = 0;
    size_t j = 0;
    for (size_t i = 0; i < s.size(); i++) {
        while (e[j] <= s[i]) { j++; used--; }
        used++;
        best = max(best, used);
    }
    return best;
}

int main() {
    cout << rooms({{9, 12}, {11, 14}, {13, 16}}) << "\n";
    cout << rooms({{9, 12}, {12, 15}}) << "\n";
    cout << rooms({{1, 10}, {2, 3}, {4, 5}}) << "\n";
}

Python:

def rooms(intervals):
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    used = best = j = 0
    for s in starts:
        while ends[j] <= s:
            j += 1
            used -= 1
        used += 1
        best = max(best, used)
    return best

print(rooms([[9, 12], [11, 14], [13, 16]]))
print(rooms([[9, 12], [12, 15]]))
print(rooms([[1, 10], [2, 3], [4, 5]]))

Both print 2, 1, 2.

Common mistakes

Mistake What you see Why Fix
last[1] = cur[1]; [[1, 10], [2, 3]] → [[1, 3]] a contained interval ends earlier last[1] = Math.max(last[1], cur[1])
No Arrays.sort before the sweep [[8, 10], [1, 3], [2, 6]] → [[8, 10]] overlapping intervals aren't neighbours sort by start first
Comparator (x, y) -> x[0] - y[0] [[2000000000, 2000000005]]: the other booking vanished int overflow (4 × 10⁹) flips the order Integer.compare(x[0], y[0])
last[1] <= cur[0] starts a new block [[1, 4], [4, 5]] stays split touching should merge in this problem new block only when last[1] < cur[0]
Comparing with the first block, or with the previous input interval wrong merges when an earlier long interval covers later ones the last merged block holds the biggest end compare with out's last element
Brute force on n = 10⁵ Time Limit Exceeded O(n²) per scan, restarts sort + sweep

Mini project: the wedding hall's free slots

The hall is open from 0 to 24. Read bookings as start end lines, merge them, and print the free slots. Walk the merged blocks with a time pointer t starting at opening time: each gap t < block.start is a free slot.

    static List<int[]> freeSlots(int[][] bookings, int open, int close) {
        List<int[]> free = new ArrayList<>();
        int t = open;
        for (int[] b : merge(bookings)) {
            if (b[0] > t) free.add(new int[]{t, b[0]});
            t = Math.max(t, b[1]);
        }
        if (t < close) free.add(new int[]{t, close});
        return free;
    }

For [[1,3],[2,6],[8,10],[15,18]] with the hall open 0 to 24 it printed [[0, 1], [6, 8], [10, 15], [18, 24]]. Extension: also print the total busy hours.

Practice

  1. Insert interval: the list [[1, 2], [3, 5], [6, 7], [9, 10]] is sorted and non-overlapping. Insert [4, 8] and merge, in O(n).
Solution

Three phases: copy the intervals that end before the new one starts, absorb every interval that starts before the new one ends, copy the rest.

    static int[][] insert(int[][] in, int[] add) {
        List<int[]> out = new ArrayList<>();
        int i = 0, n = in.length;
        while (i < n && in[i][1] < add[0]) out.add(in[i++]);
        int s = add[0], e = add[1];
        while (i < n && in[i][0] <= e) {
            s = Math.min(s, in[i][0]);
            e = Math.max(e, in[i][1]);
            i++;
        }
        out.add(new int[]{s, e});
        while (i < n) out.add(in[i++]);
        return out.toArray(new int[0][]);
    }

It printed [[1, 2], [3, 8], [9, 10]], and [[4, 8]] when the list is empty. No sort needed: O(n).

  1. Free slots: print the free slots of the wedding hall between opening and closing time.
Solution

See the mini project: merge, then walk the blocks with a time pointer. Output [[0, 1], [6, 8], [10, 15], [18, 24]].

  1. Merge only when intervals really overlap: [1, 4] and [4, 5] should stay separate.
Solution

Start a new block when last[1] <= cur[0] (instead of <). On [[1, 4], [4, 5], [2, 3]] it printed [[1, 4], [4, 5]].

  1. Interval list intersections: two lists, each sorted and non-overlapping. Return their intersections.
Solution

Two pointers. The overlap of a[i] and b[j] is [max(starts), min(ends)] if it is not empty; then move past whichever interval ends first.

    static int[][] intersect(int[][] a, int[][] b) {
        List<int[]> out = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.length && j < b.length) {
            int lo = Math.max(a[i][0], b[j][0]);
            int hi = Math.min(a[i][1], b[j][1]);
            if (lo <= hi) out.add(new int[]{lo, hi});
            if (a[i][1] < b[j][1]) i++; else j++;
        }
        return out.toArray(new int[0][]);
    }

[[0, 2], [5, 10]] and [[1, 5], [8, 12]] printed [[1, 2], [5, 5], [8, 10]]. O(n + m).

Quick quiz

What does merge(new int[][]{{1, 4}, {5, 6}}) print (with Arrays.deepToString)?

  • [[1, 6]]
  • [[1, 4], [5, 6]]
  • [[1, 5], [5, 6]]
  • [[5, 6]]
Answer

[[1, 4], [5, 6]]. last[1] = 4 < cur[0] = 5, so [5, 6] starts a new block. They don't touch: 4 and 5 are different times. (Real output: [[1, 4], [5, 6]].)

Interview questions

  1. Why sort by start, not by end? After sorting by start, an interval can only overlap the last merged block, so one comparison per interval is enough. (Sorting by end works for other problems, like picking the most non-overlapping intervals.)
  2. What is the time complexity? O(n log n) for the sort plus O(n) for the sweep.
  3. Can you do it without sorting? Only if the input is already sorted, or the coordinates are small (then mark a timeline array, like counting sort). In general, sorting is the bottleneck.
  4. Why Integer.compare instead of a[0] - b[0]? Subtraction can overflow for large or negative values and give the wrong order.
  5. Does [1,4] and [4,5] merge? In this problem yes (touching counts). Always ask the interviewer.
  6. How do you count the meeting rooms needed? Sort starts and ends separately and sweep (or use a min-heap of end times): the maximum number of overlapping intervals at any moment.
  7. Insert into an already merged, sorted list? Three phases in O(n): before, overlapping, after.
  8. What's the space complexity? O(n) for the output; Arrays.sort on objects (TimSort) also uses up to O(n) temporary space.

Glossary

Term Meaning
Interval A range with a start and an end, here int[]{start, end}
Overlap Two intervals share at least one point: a.start <= b.end && b.start <= a.end
Touching intervals One ends exactly where the next starts, like [1,4] and [4,5]
Contained interval An interval completely inside another, like [2,3] inside [1,10]
Merged interval / block One interval covering a group of overlapping ones: [min start, max end]
Brute force Trying every possibility directly, without a clever idea
Labelled break break label; leaves the loop marked with that label, even from an inner loop
Sweep One pass over the sorted data, keeping a little state (here the last block)
Comparator A function that tells the sort which of two elements comes first (negative, zero or positive)
Lambda A short unnamed function, like (x, y) -> Integer.compare(x[0], y[0])
Integer.compare(a, b) Returns negative, zero or positive without overflowing
Integer overflow A result too big for the type wraps around to a wrong (often negative) value
Arrays.deepToString Prints a 2D array like [[1, 6], [8, 10]]
Meeting rooms Find the most intervals overlapping at one moment (rooms or halls needed)
O(n log n) The cost of a good comparison sort: 1 lakh items take milliseconds
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Two intervals overlap when each starts before the other ends; in this problem, touching counts.
  • The brute force compares every pair and restarts after each merge: O(n²) per scan, up to O(n³). One lakh bookings time out.
  • Sort by start, and overlapping intervals become neighbours: compare each interval only with the last merged block, and extend its end with Math.max.
  • O(n log n) time, O(n) space. Use Integer.compare in the comparator.
  • Follow-up: meeting rooms = sort starts and ends separately and count the most events at once.

Next episode: Linked lists: reverse a list, iterative and recursive.