AdvancedData Structures & Algorithms · Lesson 39 of 40 · Updated ·
Interval Problems — Merge, Insert, Meeting Rooms and Platforms
An interval is a range with a start and an end, written [start, end]: a class from 9 to 11, a train at the platform from 09:40 to 12:00, a booking of a seminar hall. Interview problems on intervals look different on the surface, but almost all of them are solved by one of three moves: sort by start, sort by end, or sweep through the start and end events in time order. This lesson covers each move with the classic problems.
1. When do two intervals overlap?
Take [a1, b1] and [a2, b2]. It is easier to say when they do not overlap: one ends before the other starts (b1 < a2 or b2 < a1). Flip that, and they overlap exactly when
a1 <= b2 and a2 <= b1
Whether touching ends count (is [1, 3] overlapping [3, 5]?) depends on the problem. For meetings, one ending at 3 and the next starting at 3 usually do not clash. Read the statement and decide between < and <= — this is the most common source of wrong answers.
def overlap(x, y):
return x[0] <= y[1] and y[0] <= x[1]
print(overlap([1, 5], [4, 8]), overlap([1, 3], [5, 7]))
print(overlap([1, 10], [3, 4]), overlap([1, 3], [3, 5]))
True False
True True
2. Merge overlapping intervals
Problem: given intervals in any order, merge all that overlap.
Idea: sort by start. Then a new interval can only overlap the last merged block, never an earlier one, because everything earlier ends before that block began. So one pass is enough:
- if the next start is ≤ the current block's end, extend the end to
max(end, next end); - otherwise close the block and start a new one.
def merge(intervals):
out = []
for s, e in sorted(intervals):
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e) # extend the current block
else:
out.append([s, e]) # start a new block
return out
print(merge([[8, 10], [1, 3], [15, 18], [2, 6], [9, 12]]))
print(merge([[1, 4], [2, 3]]))
print(merge([[1, 2], [3, 4]]))
[[1, 6], [8, 12], [15, 18]]
[[1, 4]]
[[1, 2], [3, 4]]
[1, 4] and [2, 3] become [1, 4], not [1, 3] — that is why we take max of the ends. Time is O(n log n) for the sort plus O(n) for the pass.
3. Insert an interval into a sorted list
Problem: the list is already sorted and non-overlapping (for example, the booked slots of a hall). Add one new booking and merge where needed.
There is no need to sort again. Walk through the list in three parts: intervals that end before the new one starts, intervals that overlap it (merge them into it), and intervals that start after it ends.
def insert(slots, new):
s, e = new
out, i, n = [], 0, len(slots)
while i < n and slots[i][1] < s: # completely before
out.append(slots[i]); i += 1
while i < n and slots[i][0] <= e: # overlapping: absorb
s, e = min(s, slots[i][0]), max(e, slots[i][1]); i += 1
out.append([s, e])
out.extend(slots[i:]) # completely after
return out
print(insert([[1, 3], [6, 9]], [2, 5]))
print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
[[1, 5], [6, 9]]
[[1, 2], [3, 10], [12, 16]]
This is O(n).
4. Sweep line: minimum platforms and meeting rooms
Problem: trains arrive and leave at given times. What is the fewest platforms the station needs so no train waits? (The same question as "how many meeting rooms are needed?")
Idea: the answer is the largest number of trains present at the same moment. Turn each train into two events: an arrival (+1) and a departure (−1). Sort all events by time and walk through them, keeping a running count. The highest count is the answer.
When an arrival and a departure happen at the same time, the order matters. If a train leaving at 11:00 frees its platform for one arriving at 11:00, process the departure first. If the problem says the platform is still busy at the departure minute, process the arrival first. The code below uses two sorted arrays and handles the common railway version, where a train arriving at the same minute as another's departure still needs its own platform:
import java.util.Arrays;
public class Main {
static int platforms(int[] arr, int[] dep) {
int[] a = arr.clone(), d = dep.clone();
Arrays.sort(a);
Arrays.sort(d);
int i = 0, j = 0, cur = 0, best = 0;
while (i < a.length) {
if (a[i] <= d[j]) { cur++; i++; } // arrival first on a tie
else { cur--; j++; }
best = Math.max(best, cur);
}
return best;
}
public static void main(String[] args) {
int[] arr = {900, 940, 950, 1100, 1500, 1800};
int[] dep = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println(platforms(arr, dep));
System.out.println(platforms(new int[]{900, 1000}, new int[]{1000, 1100}));
System.out.println(platforms(new int[]{100, 200, 300}, new int[]{150, 250, 350}));
}
}
3
2
1
Sorting arrivals and departures separately is allowed because we only need the count at each moment, not which train is which. Time is O(n log n).
5. Most non-overlapping meetings (greedy by end time)
Problem: one seminar hall, many meeting requests. Choose the largest number of meetings that do not overlap. A twin question: "remove the fewest intervals so the rest do not overlap" — the answer is n − (largest non-overlapping set).
Greedy rule: sort by end time and always take the meeting that finishes first among those that still fit. Finishing early leaves the most room for the rest. (Sorting by start fails: one long early meeting can block many short ones. Sorting by length also fails on some inputs.)
def max_meetings(meetings):
count, last_end = 0, float('-inf')
for s, e in sorted(meetings, key=lambda m: m[1]): # by end time
if s >= last_end: # starts after the last chosen one ends
count += 1
last_end = e
return count
talks = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]
print(max_meetings(talks))
print(len(talks) - max_meetings(talks), "to remove")
print(max_meetings([[1, 100], [2, 3], [4, 5], [6, 7]]))
4
7 to remove
3
In the last line, sorting by start would take [1, 100] first and get only 1 meeting; sorting by end gets 3.
6. Pattern guide
| Question | Move | Time |
|---|---|---|
| Merge overlapping intervals | sort by start, one pass | O(n log n) |
| Insert into a sorted list | three-part walk | O(n) |
| Can one person attend all meetings? | sort by start, check start < previous end | O(n log n) |
| Fewest rooms / platforms | sweep events, running count (or a min-heap of end times) | O(n log n) |
| Most non-overlapping / fewest removals | sort by end, greedy | O(n log n) |
| Common free time, intersection of two lists | two pointers on sorted lists | O(n + m) |
Common mistakes
- Not sorting first. Merging and greedy choices only work on sorted input.
- Using the wrong comparison for touching ends (
<versus<=); decide from the statement. - In merge, setting the end to the new interval's end instead of the
maxof both ends. - Sorting by start for the "most meetings" problem — it must be by end.
- Changing the input list in place when the caller still needs it; sort a copy if in doubt.
Quick recap
- Overlap test:
a1 <= b2 and a2 <= b1(adjust for touching ends). - Merge: sort by start; extend the last block or start a new one.
- Insert: before / overlapping / after, O(n).
- Rooms and platforms: sweep +1 and −1 events; the peak count is the answer.
- Most non-overlapping meetings: sort by end, take each meeting that fits.