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
aandboverlap whena.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:
curstarts 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
- 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).
- 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]].
- 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]].
- 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
- 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.)
- What is the time complexity? O(n log n) for the sort plus O(n) for the sweep.
- 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.
- Why
Integer.compareinstead ofa[0] - b[0]? Subtraction can overflow for large or negative values and give the wrong order. - Does
[1,4]and[4,5]merge? In this problem yes (touching counts). Always ask the interviewer. - 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.
- Insert into an already merged, sorted list? Three phases in O(n): before, overlapping, after.
- What's the space complexity? O(n) for the output;
Arrays.sorton 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.comparein 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.