Fewest meeting rooms for a day of meetings
Each meeting is a pair [start, end] with start < end, running from
start up to end. A meeting that ends at time t frees its room for one that starts
at t. Return the smallest number of rooms that lets every meeting take place.
Examples
| Input | Output | Why |
|---|---|---|
meetings = [[0, 30], [5, 10], [15, 20]] | 2 | The long meeting needs a room all day; the other two can share a second. |
meetings = [[1, 5], [5, 10]] | 1 | The second starts exactly when the first ends. |
meetings = [[1, 10], [2, 9], [3, 8], [4, 7]] | 4 | All four are running at time 4. |
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ start < end ≤ 10⁹
Hints
Hint 1
Forget which meeting goes in which room. What single number about the day decides how many rooms you need?
Hint 2
It is the largest number of meetings running at the same moment. That number only changes when a meeting starts or ends.
Hint 3
Sort the start times and the end times separately. Walk through the starts; before each one, release every room whose meeting has ended by then.
Where people lose marks
- Using < instead of ≤ when comparing an end with a start, which counts back-to-back meetings as overlapping.
- Counting overlapping pairs: three meetings that pairwise overlap at different times may still need only two rooms.
- Sorting the meetings once by start and comparing only neighbours: a long early meeting can overlap many later ones.
Dry run on [[1,3],[2,4],[3,5],[4,6]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5starts10213243ends30415263rooms0
Starts sorted: 1, 2, 3, 4. Ends sorted: 3, 4, 5, 6. No rooms are open yet.
-
Step 2 / 5starts10213243ends30415263rooms1
A meeting starts at 1, before the earliest end (3). Every room is busy: open another. Rooms: 1.
-
Step 3 / 5starts10213243ends30415263rooms2
A meeting starts at 2, before the earliest end (3). Every room is busy: open another. Rooms: 2.
-
Step 4 / 5starts10213243ends30415263rooms2
A meeting starts at 3. The earliest end, 3, is no later than 3, so that room is free: reuse it. Still 2 rooms.
-
Step 5 / 5starts10213243ends30415263rooms2
A meeting starts at 4. The earliest end, 4, is no later than 4, so that room is free: reuse it. Still 2 rooms. Every meeting has a room: 2 in all.
How to think about it
Assigning meetings to rooms looks like a scheduling problem, but the answer is one number: the most meetings in progress at any instant. You can never use fewer rooms than that, and a room can always be reused the moment its meeting ends, so you never need more.
That count only changes at start and end times. Sort the starts and the ends separately and walk through the starts in order. Before handling a start at time t, every meeting whose end is at most t has finished, so advance the end pointer past them. Then the new meeting either reuses one of those freed rooms or needs a new one:
- If an earlier meeting has ended by now (
ends[j] ≤ start), reuse its room and movejon. - Otherwise every room is busy: open another.
Sorting is O(n log n); the walk is O(n). A min-heap of end times gives the same answer and also tells you which room each meeting gets.
Ties decide correctness: with half-open meetings, an end at t must be processed
before a start at t. That is why the test is ≤, not <.
Complexity. Time O(n log n) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_meeting_rooms(meetings):
starts = sorted(s for s, _ in meetings)
ends = sorted(e for _, e in meetings)
rooms = j = 0
for s in starts:
if ends[j] <= s: # a meeting has finished: reuse its room
j += 1
else: # every room is busy: open another
rooms += 1
return rooms#include <vector>
#include <algorithm>
int solve(const std::vector<std::vector<int>>& meetings) {
std::vector<int> starts, ends;
for (const auto& m : meetings) { starts.push_back(m[0]); ends.push_back(m[1]); }
std::sort(starts.begin(), starts.end());
std::sort(ends.begin(), ends.end());
int rooms = 0;
size_t j = 0;
for (int s : starts) {
if (ends[j] <= s) ++j; // a meeting has finished: reuse its room
else ++rooms; // every room is busy: open another
}
return rooms;
}class Solution {
public int minMeetingRooms(int[][] meetings) {
int n = meetings.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
java.util.Arrays.sort(starts);
java.util.Arrays.sort(ends);
int rooms = 0, j = 0;
for (int s : starts) {
if (ends[j] <= s) j++; // a meeting has finished: reuse its room
else rooms++; // every room is busy: open another
}
return rooms;
}
}function minMeetingRooms(meetings) {
const starts = meetings.map(m => m[0]).sort((a, b) => a - b);
const ends = meetings.map(m => m[1]).sort((a, b) => a - b);
let rooms = 0, j = 0;
for (const s of starts) {
if (ends[j] <= s) j++; // a meeting has finished: reuse its room
else rooms++; // every room is busy: open another
}
return rooms;
}fn solve(meetings: &[[i64; 2]]) -> i64 {
let mut starts: Vec<i64> = meetings.iter().map(|m| m[0]).collect();
let mut ends: Vec<i64> = meetings.iter().map(|m| m[1]).collect();
starts.sort();
ends.sort();
let (mut rooms, mut j) = (0, 0);
for s in starts {
if ends[j] <= s {
j += 1; // a meeting has finished: reuse its room
} else {
rooms += 1; // every room is busy: open another
}
}
rooms
}import Data.List (sort)
-- Walk the sorted starts; reuse a room when the earliest unclaimed end has passed.
solve :: [[Int]] -> Int
solve meetings = go (sort [s | [s, _] <- meetings]) (sort [e | [_, e] <- meetings])
where
go [] _ = 0
go (s : ss) ends@(e : es)
| e <= s = go ss es
| otherwise = 1 + go ss ends
go _ [] = 0
Variants to try
- Return the room each meeting is given: keep a min-heap of (end time, room number).
- Report the busiest time of day: record the moment the count reaches its maximum.
- Meetings have a minimum gap of g minutes for cleaning: compare ends[j] + g with the start.
Next problems
Total time covered by a set of bookings
Overlapping bookings must not be counted twice. Sort by start time and one pass merges them into blocks.
Open the problem → Medium18 minFewest bookings to cancel so none overlap
Keeping the most bookings means removing the fewest. Sort by end time and keep every booking that fits.
Open the problem → Hard30 minMost profit from jobs that do not overlap
Each job has a value, so ending earliest is no longer safe. Sort by end time; each job either joins the best schedule ending before it starts, or is skipped.
Open the problem →Write a solution and run it against the real test table.
Keep going
Total time covered by a set of bookings
Overlapping bookings must not be counted twice. Sort by start time and one pass merges them into blocks.
Open the problem → Medium18 minFewest bookings to cancel so none overlap
Keeping the most bookings means removing the fewest. Sort by end time and keep every booking that fits.
Open the problem → Hard30 minMost profit from jobs that do not overlap
Each job has a value, so ending earliest is no longer safe. Sort by end time; each job either joins the best schedule ending before it starts, or is skipped.
Open the problem → IntervalsThe pattern behind it
Sort by start to merge and count overlaps; sort by end to choose. One sorted pass replaces checking every pair.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.