Interval Problems: Merge Intervals, Meeting Rooms & Code

An interval is a range on a line with a start and an end: a meeting, a train at a platform, a hotel booking. Interval questions come in a few shapes — merge the ones that overlap, fit a new one into a schedule, count how many run at the busiest moment, remove the fewest so that nothing clashes — and almost all of them are solved by the same two moves: sort, then sweep once from left to right. Each interval is a pair [start, end], so the input is a 2D array.

Everything starts with one question: do two intervals overlap? It is easier to say when they do not — one ends before the other starts — and the overlap test is the negation of that.

Settle what the end point means before you write a comparison. A closed interval [start, end] includes both ends, so [1, 4] and [4, 5] overlap, as in Merge Intervals. A half-open interval [start, end) stops just before its end, so a meeting ending at 10 frees the room for one starting at 10, as in the meeting-room problems. A phrase such as "touching intervals merge" tells you which you have.

Why comparing every pair is too slow

The direct way to merge compares every pair, combines any two that overlap, and repeats until nothing changes. One round is n × (n − 1) / 2 comparisons — five billion for n = 100,000 — and one round is not enough, because merging creates new overlaps: [1, 3] misses [5, 8], but once [2, 6] joins it, [1, 6] reaches [5, 8]. In the order given, overlapping intervals can sit anywhere in the list. Sorting fixes exactly that.

The idea: sort by start, then sweep

• Sort by start, and keep one open block: the merged interval being built.
• If the next interval starts at or before the block's end, it overlaps: the end becomes max(end, its end), so an interval lying inside the block cannot shrink it.
• Otherwise the block is finished: output it and open a new one.

The sort is O(n log n) and the sweep looks at each interval once: about two million steps for n = 100,000 instead of billions.

1. Each interval is a bar on the number line, in the order given. Two intervals overlap when one starts before the other ends, but in this order overlapping bars can sit far apart in the list.
2. Sort by start: [1, 3], [2, 6], [8, 10], [9, 12], [15, 18]. Now anything that overlaps the interval being built comes straight after it, so one sweep from left to right finds every merge.
3. The sweep opens the first merged interval with [1, 3]. Its end, 3, is what the next start gets compared with.
4. [2, 6] starts at 2, not past the end 3, so it overlaps: the merged interval grows to [1, 6], its end now max(3, 6) = 6.
5. [8, 10] starts at 8, past the end 6. Starts only grow from here, so nothing later can reach back: [1, 6] is final, and a new merged interval opens at [8, 10].
6. [9, 12] starts at 9, not past the end 10, so it overlaps: the merged interval grows to [8, 12], its end now max(10, 12) = 12.
7. [15, 18] starts at 15, past the end 12. Starts only grow from here, so nothing later can reach back: [8, 12] is final, and a new merged interval opens at [15, 18].
8. The sweep ends with [1, 6], [8, 12] and [15, 18]: 5 intervals merged into 3. Sorting is O(n log n) and the sweep O(n), so O(n log n) in all.

Why one pass is enough

The sweep closes a block the moment a start passes its end and never looks at it again. That is safe only because of the sort: every interval still to come starts at that start or later, so none can reach back.

1. Sorted by start, the left ends form a staircase that only goes right: 1, 2, 8, 9 and 15. Whatever comes later in the list starts no earlier than whatever came before it.
2. [8, 10] starts at 8, past the block's end 6. Every interval still to come (3 of them, shaded) starts at 8 or later, so none can reach back: [1, 6] is final.
3. [15, 18] starts at 15, past the block's end 12. Every interval still to come (1 of them, shaded) starts at 15 or later, so none can reach back: [8, 12] is final.
4. Skip the sort and the promise breaks. In the order given, [2, 6] is closed as soon as [8, 10] arrives — then [1, 3] comes along and overlaps it, too late to join.

That gives the sweep its invariant: after the first k intervals in sorted order, the output holds exactly their merged groups, and every block already output is final. The decision for each interval needs only the one block still open — the shape of every sweep in this lesson: sort so that everything behind you fits in a variable or two.

The code

The open block is simply the last interval in the output list. The second input tests both boundaries: [1, 4] and [4, 5] touch, and [2, 3] lies inside [1, 4].

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

// Merges every group of overlapping closed intervals ([1, 4] and [4, 5] touch, so they merge).
vector<vector<int>> mergeIntervals(vector<vector<int>> intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    vector<vector<int>> merged;
    for (const vector<int>& iv : intervals) {
        if (!merged.empty() && iv[0] <= merged.back()[1]) {
            // starts inside the open block: extend it (max, in case iv lies wholly inside)
            merged.back()[1] = max(merged.back()[1], iv[1]);
        } else {
            merged.push_back(iv);  // starts after the block ends: nothing later can reach back
        }
    }
    return merged;
}

string show(const vector<vector<int>>& list) {
    string out;
    for (const vector<int>& iv : list) {
        if (!out.empty()) out += " ";
        out += "[" + to_string(iv[0]) + ", " + to_string(iv[1]) + "]";
    }
    return out;
}

int main() {
    vector<vector<vector<int>>> inputs = {
        {{2, 6}, {8, 10}, {1, 3}, {15, 18}, {9, 12}},
        {{1, 4}, {4, 5}, {2, 3}},
    };
    for (const vector<vector<int>>& intervals : inputs) {
        cout << "Input:  " << show(intervals) << "\n";
        cout << "Merged: " << show(mergeIntervals(intervals)) << "\n";
    }
    return 0;
}

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

public class Main {
    // Merges every group of overlapping closed intervals ([1, 4] and [4, 5] touch, so they merge).
    static List<int[]> mergeIntervals(int[][] intervals) {
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] iv : sorted) {
            if (!merged.isEmpty() && iv[0] <= merged.get(merged.size() - 1)[1]) {
                // starts inside the open block: extend it (max, in case iv lies wholly inside)
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], iv[1]);
            } else {
                merged.add(new int[] {iv[0], iv[1]}); // a copy, so extending it never edits the input
            }
        }
        return merged;
    }

    static String show(List<int[]> list) {
        StringBuilder out = new StringBuilder();
        for (int[] iv : list) {
            if (out.length() > 0) out.append(" ");
            out.append("[").append(iv[0]).append(", ").append(iv[1]).append("]");
        }
        return out.toString();
    }

    public static void main(String[] args) {
        int[][][] inputs = {
            {{2, 6}, {8, 10}, {1, 3}, {15, 18}, {9, 12}},
            {{1, 4}, {4, 5}, {2, 3}},
        };
        for (int[][] intervals : inputs) {
            System.out.println("Input:  " + show(Arrays.asList(intervals)));
            System.out.println("Merged: " + show(mergeIntervals(intervals)));
        }
    }
}

def merge_intervals(intervals):
    """Merge every group of overlapping closed intervals ([1, 4] and [4, 5] touch, so they merge)."""
    merged = []
    for start, end in sorted(intervals, key=lambda iv: iv[0]):
        if merged and start <= merged[-1][1]:
            # starts inside the open block: extend it (max, in case it lies wholly inside)
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])  # starts after the block ends: nothing later can reach back
    return merged


def show(intervals):
    return " ".join(f"[{s}, {e}]" for s, e in intervals)


inputs = [
    [[2, 6], [8, 10], [1, 3], [15, 18], [9, 12]],
    [[1, 4], [4, 5], [2, 3]],
]
for intervals in inputs:
    print("Input: ", show(intervals))
    print("Merged:", show(merge_intervals(intervals)))

// Merges every group of overlapping closed intervals ([1, 4] and [4, 5] touch, so they merge).
function mergeIntervals(intervals) {
  const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) {
      // starts inside the open block: extend it (max, in case it lies wholly inside)
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]); // starts after the block ends: nothing later can reach back
    }
  }
  return merged;
}

const show = (list) => list.map(([s, e]) => `[${s}, ${e}]`).join(" ");

const inputs = [
  [[2, 6], [8, 10], [1, 3], [15, 18], [9, 12]],
  [[1, 4], [4, 5], [2, 3]],
];
for (const intervals of inputs) {
  console.log(`Input:  ${show(intervals)}`);
  console.log(`Merged: ${show(mergeIntervals(intervals))}`);
}

Input:  [2, 6] [8, 10] [1, 3] [15, 18] [9, 12]
Merged: [1, 6] [8, 12] [15, 18]
Input:  [1, 4] [4, 5] [2, 3]
Merged: [1, 5]

Change <= to < and touching intervals stay apart — right for half-open meetings, wrong for Merge Intervals.

Inserting and intersecting sorted lists

When the input is already sorted, the sweep alone is the job. Insert Interval adds one interval to a sorted, non-overlapping list in O(n): copy what ends before it, absorb what overlaps it, copy the rest. The absorbed intervals are consecutive because the list is sorted.

1. The list is sorted and no two of its intervals overlap. The new interval [4, 8] has to go in, merging with whatever it touches; its start and end are the two lines to compare against.
2. [1, 2] ends at 2, before the new start 4: it cannot touch the new interval, so it is copied to the result unchanged.
3. [3, 5] starts at 3, not after the new end 8: it overlaps, so it is absorbed and the new interval grows to [3, 8].
4. [6, 7] lies inside [3, 8]: absorbed, and the new interval stays as it is.
5. [8, 10] starts at 8, not after the new end 8: it overlaps, so it is absorbed and the new interval grows to [3, 10].
6. [12, 16] starts at 12, after the new end 10. Sorted order means everything from here on does too, so [3, 10] takes its place and the rest is copied as it is.
7. Result: [1, 2], [3, 10], [12, 16]. One pass over a list that was already sorted: O(n), with no sort at all.

Interval List Intersections asks for every stretch covered by both of two sorted lists: a walk with two pointers, one per list. The interval that ends first can meet nothing else in the other list, whose later intervals all start after it ends, so its pointer moves. That makes the walk O(n + m).

1. Each list is sorted and its own intervals never overlap. One pointer walks A, one walks B; at each step the common part of the two current intervals runs from the later start to the earlier end.
2. [1, 4] and [2, 7]: lo = 2, hi = 4, so [2, 4] is covered by both. [1, 4] ends first and can meet nothing else in the other list, so its pointer moves on; [2, 7] stays.
3. [6, 9] and [2, 7]: lo = 6, hi = 7, so [6, 7] is covered by both. [2, 7] ends first and can meet nothing else in the other list, so its pointer moves on; [6, 9] stays.
4. [6, 9] and [8, 11]: lo = 8, hi = 9, so [8, 9] is covered by both. [6, 9] ends first and can meet nothing else in the other list, so its pointer moves on; [8, 11] stays.
5. [13, 16] and [8, 11]: lo = 13, hi = 11 — lo is past hi, nothing in common. [8, 11] ends first and can meet nothing else in the other list, so its pointer moves on; [13, 16] stays.
6. [13, 16] and [12, 15]: lo = 13, hi = 15, so [13, 15] is covered by both. [12, 15] ends first and can meet nothing else in the other list, so its pointer moves on; [13, 16] stays.
7. B is used up, so nothing more can overlap. 4 common stretches: [2, 4], [6, 7], [8, 9], [13, 15]. Each step moves one pointer, so the walk is O(n + m).

Meeting rooms: counting the overlap

Meeting Rooms asks whether one person can attend everything: sort by start and compare each meeting with the one before it. Neighbours are enough, because if any two meetings overlap, the first also overlaps the meeting straight after it.

Meeting Rooms II asks how many rooms are needed: the largest number of meetings running at one moment. That many are necessary, since those meetings run at once, and enough, because a new room opens only when every room is busy. So you want the peak of a running count — a sweep line, +1 at every start and −1 at every end. Only when matters, not which meeting, so starts and ends are sorted as separate lists.

1. Five half-open meetings. Only the times matter, so the starts (0, 5, 10, 15, 20) and the ends (10, 20, 25, 30, 35) are sorted as two separate lists and walked like a merge.
2. A start at 0: [0, 30] begins and the count rises to 1. New peak: 1.
3. A start at 5: [5, 10] begins and the count rises to 2. New peak: 2.
4. An end at 10, tied with a start: [5, 10] is over and frees its room, so the count drops to 1. Half-open meetings let the end go first.
5. A start at 10: [10, 20] begins and the count rises to 2.
6. A start at 15: [15, 25] begins and the count rises to 3. New peak: 3.
7. An end at 20, tied with a start: [10, 20] is over and frees its room, so the count drops to 2. Half-open meetings let the end go first.
8. A start at 20: [20, 35] begins and the count rises to 3.
9. Every start has been seen, so the count can only fall and the loop stops. The peak, 3, is the answer: at time 20 these 3 meetings run at once, and no moment has more.
10. Treat the same meetings as closed — a train arriving as another leaves still needs a platform — and a tie goes to the start. At time 20, 4 intervals contain the point 20, so the answer becomes 4.

Ties carry the boundary rule: for half-open meetings an end at t goes before a start at t; for closed intervals, as in Minimum Number of Platforms, the start goes first. The function takes that rule as a flag.

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

// The most intervals in progress at one moment: the rooms (or platforms) needed.
// closed = true: an interval ending at t still clashes with one starting at t.
int minRooms(const vector<vector<int>>& intervals, bool closed) {
    vector<int> starts, ends;
    for (const vector<int>& iv : intervals) {
        starts.push_back(iv[0]);
        ends.push_back(iv[1]);
    }
    sort(starts.begin(), starts.end());  // only the times matter, not which meeting they
    sort(ends.begin(), ends.end());      // belong to, so starts and ends are sorted apart
    int n = (int)starts.size(), i = 0, j = 0, inUse = 0, peak = 0;
    while (i < n) {
        // on a tie, a half-open meeting leaves before the next arrives; a closed one stays
        bool startFirst = closed ? starts[i] <= ends[j] : starts[i] < ends[j];
        if (startFirst) {
            inUse++;
            i++;
            peak = max(peak, inUse);
        } else {
            inUse--;
            j++;
        }
    }
    return peak;
}

int main() {
    vector<vector<int>> meetings = {{0, 30}, {5, 10}, {10, 20}, {15, 25}, {20, 35}};
    cout << "Meetings:";
    for (const vector<int>& m : meetings) cout << " [" << m[0] << ", " << m[1] << "]";
    cout << "\n";
    cout << "Rooms, half-open [start, end): " << minRooms(meetings, false) << "\n";
    cout << "Platforms, closed [start, end]: " << minRooms(meetings, true) << "\n";
    return 0;
}

import java.util.Arrays;

public class Main {
    // The most intervals in progress at one moment: the rooms (or platforms) needed.
    // closed = true: an interval ending at t still clashes with one starting at t.
    static int minRooms(int[][] intervals, boolean closed) {
        int n = intervals.length;
        int[] starts = new int[n], ends = new int[n];
        for (int k = 0; k < n; k++) {
            starts[k] = intervals[k][0];
            ends[k] = intervals[k][1];
        }
        Arrays.sort(starts); // only the times matter, not which meeting they
        Arrays.sort(ends);   // belong to, so starts and ends are sorted apart
        int i = 0, j = 0, inUse = 0, peak = 0;
        while (i < n) {
            // on a tie, a half-open meeting leaves before the next arrives; a closed one stays
            boolean startFirst = closed ? starts[i] <= ends[j] : starts[i] < ends[j];
            if (startFirst) {
                inUse++;
                i++;
                peak = Math.max(peak, inUse);
            } else {
                inUse--;
                j++;
            }
        }
        return peak;
    }

    public static void main(String[] args) {
        int[][] meetings = {{0, 30}, {5, 10}, {10, 20}, {15, 25}, {20, 35}};
        StringBuilder line = new StringBuilder("Meetings:");
        for (int[] m : meetings) line.append(" [").append(m[0]).append(", ").append(m[1]).append("]");
        System.out.println(line);
        System.out.println("Rooms, half-open [start, end): " + minRooms(meetings, false));
        System.out.println("Platforms, closed [start, end]: " + minRooms(meetings, true));
    }
}

def min_rooms(intervals, closed):
    """The most intervals in progress at one moment: the rooms (or platforms) needed.
    closed=True: an interval ending at t still clashes with one starting at t."""
    starts = sorted(s for s, _ in intervals)  # only the times matter, not which meeting they
    ends = sorted(e for _, e in intervals)    # belong to, so starts and ends are sorted apart
    i = j = in_use = peak = 0
    while i < len(starts):
        # on a tie, a half-open meeting leaves before the next arrives; a closed one stays
        start_first = starts[i] <= ends[j] if closed else starts[i] < ends[j]
        if start_first:
            in_use += 1
            i += 1
            peak = max(peak, in_use)
        else:
            in_use -= 1
            j += 1
    return peak


meetings = [[0, 30], [5, 10], [10, 20], [15, 25], [20, 35]]
print("Meetings:", " ".join(f"[{s}, {e}]" for s, e in meetings))
print("Rooms, half-open [start, end):", min_rooms(meetings, False))
print("Platforms, closed [start, end]:", min_rooms(meetings, True))

// The most intervals in progress at one moment: the rooms (or platforms) needed.
// closed = true: an interval ending at t still clashes with one starting at t.
function minRooms(intervals, closed) {
  const starts = intervals.map((iv) => iv[0]).sort((a, b) => a - b); // only the times matter, not which
  const ends = intervals.map((iv) => iv[1]).sort((a, b) => a - b); // meeting they belong to
  let i = 0;
  let j = 0;
  let inUse = 0;
  let peak = 0;
  while (i < starts.length) {
    // on a tie, a half-open meeting leaves before the next arrives; a closed one stays
    const startFirst = closed ? starts[i] <= ends[j] : starts[i] < ends[j];
    if (startFirst) {
      inUse++;
      i++;
      peak = Math.max(peak, inUse);
    } else {
      inUse--;
      j++;
    }
  }
  return peak;
}

const meetings = [[0, 30], [5, 10], [10, 20], [15, 25], [20, 35]];
console.log(`Meetings: ${meetings.map(([s, e]) => `[${s}, ${e}]`).join(" ")}`);
console.log(`Rooms, half-open [start, end): ${minRooms(meetings, false)}`);
console.log(`Platforms, closed [start, end]: ${minRooms(meetings, true)}`);

Meetings: [0, 30] [5, 10] [10, 20] [15, 25] [20, 35]
Rooms, half-open [start, end): 3
Platforms, closed [start, end]: 4

A min-heap of the rooms' end times gives the same answer in O(n log n) and can say which room each meeting gets. Car Pooling is the sweep with weights, and with small whole-number stops a difference array — the prefix sum idea run backwards — does it without sorting.

Removing overlaps: keep the interval that ends first

Non-overlapping Intervals asks for the fewest removals so that nothing overlaps — the same as keeping the most. Sorting by start fails here; the greedy algorithm that works sorts by end and keeps each interval that starts at or after the last kept end.

1. Keep as many intervals as possible with no two overlapping. Sorted by start and kept greedily, [1, 10] goes first — and it blocks everything else: 1 kept, 3 removed.
2. Sort by end instead. Why is the earliest end, [2, 3], a safe first pick? Any first pick ends no earlier — [1, 10] ends at 10 — so swapping in [2, 3] frees more room after it and breaks nothing.
3. Nothing is kept yet, so [2, 3], the earliest end, is kept. The kept end becomes 3: the next interval must start there or later.
4. [4, 5] starts at 4, at or after the kept end 3: keep it. The kept end becomes 5.
5. [6, 7] starts at 6, at or after the kept end 5: keep it. The kept end becomes 7.
6. [1, 10] starts at 1, before the kept end 7: it clashes, so it is the one removed.
7. 3 kept, 1 removed — against 1 kept when sorted by start. The same loop, with a strict comparison for closed ends, counts the arrows in the balloon problem.

The proof is an exchange argument: in any best selection, swap the first interval for the one that ends earliest overall. Everything else started after the old first one ended, so also after the new one ends — still valid, same size. Repeat on the rest. With closed ends and a strict comparison, the same loop counts the arrows in Minimum Number of Arrows to Burst Balloons.

Time and space complexity

The sort is nearly always the expensive part; when the input arrives sorted, the sweep alone is the cost.

How to recognise an interval problem

• The input is pairs that are ranges: [start, end], arrival and departure times.
• The statement says overlap, conflict, merge, book or schedule.
• It asks for a maximum at any moment — rooms, platforms: a sweep line.
• It asks for the most you can keep or the fewest to remove: the earliest-end greedy.
• Two sorted lists of ranges must be combined: two pointers.

Common mistakes

• Closed against half-open: <= or < decides whether [1, 4] and [4, 5] merge.
• No max when extending: [1, 10] then [2, 3] must not become [1, 3].
• Dropping the last block when the open block lives in its own variable.
• The wrong sort key: merging sorts by start, keeping the most sorts by end.
• A broken comparator: JavaScript's bare sort() compares pairs as strings; Java's a[0] - b[0] can overflow, Integer.compare cannot.

Practice in this order

1. Meeting Rooms: sort and compare neighbours.
2. Merge Intervals: the sort-and-sweep above.
3. Insert Interval: three phases, no sort needed.
4. Interval List Intersections: two pointers.
5. Meeting Rooms II: the sweep line.
6. Minimum Number of Platforms: the count with closed intervals.
7. Non-overlapping Intervals: the earliest-end greedy.
8. Minimum Number of Arrows to Burst Balloons: the greedy with closed ends.
9. Car Pooling: a weighted sweep against a capacity.

The intervals problem list has every interval problem in the catalogue, easiest first. When the first five feel routine, the next stage is the heap: a second way to solve Meeting Rooms II and a tool for every "keep the k best" question.