You run a shared office. People book meetings as time intervals, and two meetings that overlap in time cannot share a room. Given the full list of bookings for the day, you want the smallest number of rooms that lets every meeting happen without any two overlapping meetings landing in the same room. That smallest number is exactly the largest number of meetings that are ever in progress at the same instant.
// intervals: Array<[start, end]>
// Each meeting is a pair of numbers. The interval is HALF-OPEN: [start, end)
// means the meeting occupies time from start up to (but not including) end.
// So a meeting that ends at t = 10 does NOT conflict with one that starts at t = 10.
// returns: number — the minimum count of rooms needed. Just the count, not an assignment.
function intervalsMinimumMeetingRooms(intervals);// Three meetings; the [0,30] meeting overlaps both of the others,
// but [5,10] and [15,20] never overlap each other. Peak concurrency is 2.
intervalsMinimumMeetingRooms([[0, 30], [5, 10], [15, 20]]); // → 2// Back-to-back meetings, each ending exactly when the next begins.
// Half-open intervals mean none of these conflict — one room handles all three.
intervalsMinimumMeetingRooms([[0, 10], [10, 20], [20, 30]]); // → 1// All three meetings are live at the same time → three rooms.
intervalsMinimumMeetingRooms([[1, 5], [2, 6], [3, 7]]); // → 3[start, end). A meeting ending at t and another starting at t do NOT overlap — they can share a room. Touching boundaries are not conflicts.intervalsMinimumMeetingRooms([]) returns 0.start < end for every interval, and all times are finite numbers.[start, end) pair.You'll count the fewest rooms an office needs to host a set of meetings, where two meetings clash only if they are live at the same instant.
People book the day full of meetings, each a [start, end) time slot. Two meetings can share a room as long as they never run at the same time. You want the smallest number of rooms that fits all of them. The key reframing: the number of rooms you need is exactly the maximum number of meetings happening simultaneously at any single instant. If at the busiest moment three meetings are all in progress, you need three rooms — no fewer, because those three must be in three different places at once; and no more, because outside that peak you have spare capacity to reuse.
Because the intervals are half-open [start, end), a meeting that ends at t = 10 and another that starts at t = 10 do not clash. They hand the room off cleanly. That boundary rule decides a surprising number of the test cases.
Draw every meeting as a horizontal bar on a timeline. Now slide a vertical line left to right across the whole day. At each position, count how many bars the line crosses. The tallest stack the line ever crosses is your answer.
So the real question is not "do these two specific meetings overlap" but "what is the peak concurrency across the whole day." Everything below is about computing that peak without checking every pair of meetings against each other.
The instinct that trips most people up is to sort by start time and then count overlaps as you scan, assuming the sorted order alone tells you the answer. A common version: sort by start, then for each meeting count how many earlier meetings it overlaps.
function naive(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
let conflicts = 0;
for (let i = 0; i < sorted.length; i++) {
for (let j = 0; j < i; j++) {
// count a clash if meeting j is still running when meeting i starts
if (sorted[j][1] > sorted[i][0]) conflicts++;
}
}
return conflicts; // this is a count of overlapping PAIRS, not rooms
}This returns the wrong quantity entirely. Run it on [[1,5],[2,6],[3,7]]: every pair overlaps, so it counts 3 clashing pairs and returns 3 — which happens to be right here only by coincidence. Run it on [[0,30],[5,10],[15,20]]: [0,30] overlaps [5,10] and overlaps [15,20] → 2 pairs, so it returns 2. Right again, by luck. Now run it on [[0,30],[1,2],[3,4],[5,6]]: the big [0,30] meeting overlaps all three short ones, giving 3 pairs, so it returns 3 — but the true answer is 2, because the three short meetings never overlap each other, so at most one runs alongside [0,30] at a time. Counting overlapping pairs is not counting rooms — a meeting that overlaps three others one-at-a-time needs two rooms, not four. The number of clashing pairs and the peak concurrency are different numbers.
The fix is to stop thinking about pairs and start thinking about the timeline: track how many meetings are live as time advances, and remember the highest that running count ever reaches.
Split the meetings into two lists — all the start times, and all the end times — and sort each list on its own. Then walk a single time cursor forward, comparing the next start against the next end. A start that comes before the next end means a new meeting opened while others are still running: increment the room count. Otherwise the earliest-ending meeting has finished: decrement. Track the maximum the count ever reaches.
function intervalsMinimumMeetingRooms(intervals) {
if (intervals.length === 0) return 0;
// Two independent sorted timelines: when meetings start, when they end.
const starts = intervals.map(([start]) => start).sort((a, b) => a - b);
const ends = intervals.map(([, end]) => end).sort((a, b) => a - b);
let rooms = 0; // meetings currently in progress
let maxRooms = 0; // the peak we've seen — this is the answer
let s = 0; // cursor into starts
let e = 0; // cursor into ends
while (s < starts.length) {
if (starts[s] < ends[e]) {
// A meeting starts before the next one ends → they overlap → open a room.
rooms++;
maxRooms = Math.max(maxRooms, rooms);
s++;
} else {
// The next start is at-or-after the next end → a room freed up first.
// (>= because [start, end) is half-open: end === start is NOT a conflict.)
rooms--;
e++;
}
}
return maxRooms;
}
module.exports = { intervalsMinimumMeetingRooms };The two big shifts from the naive version: first, we sort starts and ends into separate lists and throw away which start paired with which end — for counting concurrency, only the order of events along the timeline matters, not which meeting owns which event. Second, we never look at pairs; we keep one running tally and watch its peak.
Two details carry the correctness. The comparison is starts[s] < ends[e] — strictly less than. That < (rather than <=) is what encodes the half-open rule: when a start equals an end, the branch falls to the else, treating it as "a room freed up first," so a meeting ending at 10 frees the room for one starting at 10. And we only loop while (s < starts.length): once every meeting has started, the count can only go down, so the peak is already locked in — there's no reason to keep draining the ends list.
Sorting two arrays of n numbers is O(n log n); the sweep is one O(n) pass. Total: O(n log n) time, O(n) extra space for the two lists.
Trace intervalsMinimumMeetingRooms([[0, 30], [5, 10], [15, 20]]).
After the split and sort: starts = [0, 5, 15], ends = [10, 20, 30]. Cursors s = 0, e = 0, with rooms = 0 and maxRooms = 0.
starts = [0, 5, 15] ends = [10, 20, 30]
s=0 e=0 starts[0]=0 < ends[0]=10 → open rooms=1 max=1
s=1 e=0 starts[1]=5 < ends[0]=10 → open rooms=2 max=2
s=2 e=0 starts[2]=15 ≥ ends[0]=10 → close rooms=1 max=2 (e→1)
s=2 e=1 starts[2]=15 < ends[1]=20 → open rooms=2 max=2
s=3 s == starts.length → loop ends
return 2
Read the busiest stretch off the trace: by the second step both [0,30] and [5,10] are open, so rooms hits 2 and maxRooms records it. Then at t = 15 the comparison 15 ≥ 10 fires the else branch — the meeting that ended at 10 ([5,10]) frees its room before [15,20] starts, so the count dips to 1 before climbing back to 2. The peak never exceeds 2, so two rooms suffice.
The touching-boundary rule is where the half-open convention earns its keep. On [[0,10],[10,20]] we get starts = [0, 10], ends = [10, 20]. Step one: 0 < 10 → open, rooms = 1. Step two: starts[1] = 10 versus ends[0] = 10 → 10 < 10 is false, so the else runs and rooms drops to 0 before the second meeting opens. The peak stays at 1 — one room hosts both, exactly as the half-open rule demands.
<= instead of <. If you write starts[s] <= ends[e], a start at t = 10 "overlaps" an end at t = 10, so back-to-back meetings [[0,10],[10,20]] would report 2 rooms. The intervals are half-open: a meeting ending at t releases the room for one starting at t. Use strict <, which sends the tie to the else (close) branch.rooms ends the loop at whatever's still running when the last meeting starts — not the peak. If you return rooms, then [[1,4],[2,5],[3,6],[10,11]] returns 1 (by the time [10,11] starts, all three earlier meetings have ended, so only it is open) when the true answer is 3 (at t = 3 all of [1,4], [2,5], [3,6] run at once). You must track maxRooms = Math.max(maxRooms, rooms) on every open. The answer is the maximum concurrency, never the final value.[start, end] pairs by start keeps each end glued to its start, so you can't compare "next start" against "globally next end." The whole trick is decoupling the two event streams: sort starts alone, sort ends alone. They are independent timelines.starts and ends are empty; without the early return 0 the loop guard s < starts.length is immediately false and maxRooms stays 0 anyway — but don't reach for ends[0] before the loop, or you'll read undefined on an empty list.ends[e] out of bounds. The loop is bounded by s < starts.length, and every close step consumes an end that some earlier open step paired against (each meeting's end sits ahead of cursor e until its room closes), so ends[e] is always defined while s is in range. If you instead loop until both cursors exhaust, you'll compare starts[s] against ends[e] === undefined after the starts run out, and number < undefined is false — corrupting the count.(endTime, roomId); for each meeting, if the earliest-freeing room is free by its start, reuse that room id, else allocate a new one. The heap of end times is the same idea as this sweep — it just remembers room identities. The heap's comparison must order by end time, and the "is it free?" check is again room.end <= meeting.start to respect the half-open boundary.true only if no two meetings overlap (peak concurrency ≤ 1). Sort by start and check each meeting begins at-or-after the previous one's end. It's this problem with the answer collapsed to a yes/no on whether the peak ever exceeds 1.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You run a shared office. People book meetings as time intervals, and two meetings that overlap in time cannot share a room. Given the full list of bookings for the day, you want the smallest number of rooms that lets every meeting happen without any two overlapping meetings landing in the same room. That smallest number is exactly the largest number of meetings that are ever in progress at the same instant.
// intervals: Array<[start, end]>
// Each meeting is a pair of numbers. The interval is HALF-OPEN: [start, end)
// means the meeting occupies time from start up to (but not including) end.
// So a meeting that ends at t = 10 does NOT conflict with one that starts at t = 10.
// returns: number — the minimum count of rooms needed. Just the count, not an assignment.
function intervalsMinimumMeetingRooms(intervals);// Three meetings; the [0,30] meeting overlaps both of the others,
// but [5,10] and [15,20] never overlap each other. Peak concurrency is 2.
intervalsMinimumMeetingRooms([[0, 30], [5, 10], [15, 20]]); // → 2// Back-to-back meetings, each ending exactly when the next begins.
// Half-open intervals mean none of these conflict — one room handles all three.
intervalsMinimumMeetingRooms([[0, 10], [10, 20], [20, 30]]); // → 1// All three meetings are live at the same time → three rooms.
intervalsMinimumMeetingRooms([[1, 5], [2, 6], [3, 7]]); // → 3[start, end). A meeting ending at t and another starting at t do NOT overlap — they can share a room. Touching boundaries are not conflicts.intervalsMinimumMeetingRooms([]) returns 0.start < end for every interval, and all times are finite numbers.[start, end) pair.You'll count the fewest rooms an office needs to host a set of meetings, where two meetings clash only if they are live at the same instant.
People book the day full of meetings, each a [start, end) time slot. Two meetings can share a room as long as they never run at the same time. You want the smallest number of rooms that fits all of them. The key reframing: the number of rooms you need is exactly the maximum number of meetings happening simultaneously at any single instant. If at the busiest moment three meetings are all in progress, you need three rooms — no fewer, because those three must be in three different places at once; and no more, because outside that peak you have spare capacity to reuse.
Because the intervals are half-open [start, end), a meeting that ends at t = 10 and another that starts at t = 10 do not clash. They hand the room off cleanly. That boundary rule decides a surprising number of the test cases.
Draw every meeting as a horizontal bar on a timeline. Now slide a vertical line left to right across the whole day. At each position, count how many bars the line crosses. The tallest stack the line ever crosses is your answer.
So the real question is not "do these two specific meetings overlap" but "what is the peak concurrency across the whole day." Everything below is about computing that peak without checking every pair of meetings against each other.
The instinct that trips most people up is to sort by start time and then count overlaps as you scan, assuming the sorted order alone tells you the answer. A common version: sort by start, then for each meeting count how many earlier meetings it overlaps.
function naive(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
let conflicts = 0;
for (let i = 0; i < sorted.length; i++) {
for (let j = 0; j < i; j++) {
// count a clash if meeting j is still running when meeting i starts
if (sorted[j][1] > sorted[i][0]) conflicts++;
}
}
return conflicts; // this is a count of overlapping PAIRS, not rooms
}This returns the wrong quantity entirely. Run it on [[1,5],[2,6],[3,7]]: every pair overlaps, so it counts 3 clashing pairs and returns 3 — which happens to be right here only by coincidence. Run it on [[0,30],[5,10],[15,20]]: [0,30] overlaps [5,10] and overlaps [15,20] → 2 pairs, so it returns 2. Right again, by luck. Now run it on [[0,30],[1,2],[3,4],[5,6]]: the big [0,30] meeting overlaps all three short ones, giving 3 pairs, so it returns 3 — but the true answer is 2, because the three short meetings never overlap each other, so at most one runs alongside [0,30] at a time. Counting overlapping pairs is not counting rooms — a meeting that overlaps three others one-at-a-time needs two rooms, not four. The number of clashing pairs and the peak concurrency are different numbers.
The fix is to stop thinking about pairs and start thinking about the timeline: track how many meetings are live as time advances, and remember the highest that running count ever reaches.
Split the meetings into two lists — all the start times, and all the end times — and sort each list on its own. Then walk a single time cursor forward, comparing the next start against the next end. A start that comes before the next end means a new meeting opened while others are still running: increment the room count. Otherwise the earliest-ending meeting has finished: decrement. Track the maximum the count ever reaches.
function intervalsMinimumMeetingRooms(intervals) {
if (intervals.length === 0) return 0;
// Two independent sorted timelines: when meetings start, when they end.
const starts = intervals.map(([start]) => start).sort((a, b) => a - b);
const ends = intervals.map(([, end]) => end).sort((a, b) => a - b);
let rooms = 0; // meetings currently in progress
let maxRooms = 0; // the peak we've seen — this is the answer
let s = 0; // cursor into starts
let e = 0; // cursor into ends
while (s < starts.length) {
if (starts[s] < ends[e]) {
// A meeting starts before the next one ends → they overlap → open a room.
rooms++;
maxRooms = Math.max(maxRooms, rooms);
s++;
} else {
// The next start is at-or-after the next end → a room freed up first.
// (>= because [start, end) is half-open: end === start is NOT a conflict.)
rooms--;
e++;
}
}
return maxRooms;
}
module.exports = { intervalsMinimumMeetingRooms };The two big shifts from the naive version: first, we sort starts and ends into separate lists and throw away which start paired with which end — for counting concurrency, only the order of events along the timeline matters, not which meeting owns which event. Second, we never look at pairs; we keep one running tally and watch its peak.
Two details carry the correctness. The comparison is starts[s] < ends[e] — strictly less than. That < (rather than <=) is what encodes the half-open rule: when a start equals an end, the branch falls to the else, treating it as "a room freed up first," so a meeting ending at 10 frees the room for one starting at 10. And we only loop while (s < starts.length): once every meeting has started, the count can only go down, so the peak is already locked in — there's no reason to keep draining the ends list.
Sorting two arrays of n numbers is O(n log n); the sweep is one O(n) pass. Total: O(n log n) time, O(n) extra space for the two lists.
Trace intervalsMinimumMeetingRooms([[0, 30], [5, 10], [15, 20]]).
After the split and sort: starts = [0, 5, 15], ends = [10, 20, 30]. Cursors s = 0, e = 0, with rooms = 0 and maxRooms = 0.
starts = [0, 5, 15] ends = [10, 20, 30]
s=0 e=0 starts[0]=0 < ends[0]=10 → open rooms=1 max=1
s=1 e=0 starts[1]=5 < ends[0]=10 → open rooms=2 max=2
s=2 e=0 starts[2]=15 ≥ ends[0]=10 → close rooms=1 max=2 (e→1)
s=2 e=1 starts[2]=15 < ends[1]=20 → open rooms=2 max=2
s=3 s == starts.length → loop ends
return 2
Read the busiest stretch off the trace: by the second step both [0,30] and [5,10] are open, so rooms hits 2 and maxRooms records it. Then at t = 15 the comparison 15 ≥ 10 fires the else branch — the meeting that ended at 10 ([5,10]) frees its room before [15,20] starts, so the count dips to 1 before climbing back to 2. The peak never exceeds 2, so two rooms suffice.
The touching-boundary rule is where the half-open convention earns its keep. On [[0,10],[10,20]] we get starts = [0, 10], ends = [10, 20]. Step one: 0 < 10 → open, rooms = 1. Step two: starts[1] = 10 versus ends[0] = 10 → 10 < 10 is false, so the else runs and rooms drops to 0 before the second meeting opens. The peak stays at 1 — one room hosts both, exactly as the half-open rule demands.
<= instead of <. If you write starts[s] <= ends[e], a start at t = 10 "overlaps" an end at t = 10, so back-to-back meetings [[0,10],[10,20]] would report 2 rooms. The intervals are half-open: a meeting ending at t releases the room for one starting at t. Use strict <, which sends the tie to the else (close) branch.rooms ends the loop at whatever's still running when the last meeting starts — not the peak. If you return rooms, then [[1,4],[2,5],[3,6],[10,11]] returns 1 (by the time [10,11] starts, all three earlier meetings have ended, so only it is open) when the true answer is 3 (at t = 3 all of [1,4], [2,5], [3,6] run at once). You must track maxRooms = Math.max(maxRooms, rooms) on every open. The answer is the maximum concurrency, never the final value.[start, end] pairs by start keeps each end glued to its start, so you can't compare "next start" against "globally next end." The whole trick is decoupling the two event streams: sort starts alone, sort ends alone. They are independent timelines.starts and ends are empty; without the early return 0 the loop guard s < starts.length is immediately false and maxRooms stays 0 anyway — but don't reach for ends[0] before the loop, or you'll read undefined on an empty list.ends[e] out of bounds. The loop is bounded by s < starts.length, and every close step consumes an end that some earlier open step paired against (each meeting's end sits ahead of cursor e until its room closes), so ends[e] is always defined while s is in range. If you instead loop until both cursors exhaust, you'll compare starts[s] against ends[e] === undefined after the starts run out, and number < undefined is false — corrupting the count.(endTime, roomId); for each meeting, if the earliest-freeing room is free by its start, reuse that room id, else allocate a new one. The heap of end times is the same idea as this sweep — it just remembers room identities. The heap's comparison must order by end time, and the "is it free?" check is again room.end <= meeting.start to respect the half-open boundary.true only if no two meetings overlap (peak concurrency ≤ 1). Sort by start and check each meeting begins at-or-after the previous one's end. It's this problem with the answer collapsed to a yes/no on whether the peak ever exceeds 1.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.