How many rooms are needed at peak
A venue schedules sessions across the day. Find the minimum number of rooms so no two overlapping sessions share one.
- Each session has a start and an end in minutes.
- Intervals are half-open: [start, end).
- Sessions that merely touch (one ends exactly when the next starts) do not conflict.
sessionRooms(starts: list<int>, ends: list<int>) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int sessionRooms(std::vector<int> starts, std::vector<int> ends) {
}Worked examples
| Call | Result |
|---|---|
sessionRooms(std::vector<int>{10}, std::vector<int>{20}) | 1 |
sessionRooms(std::vector<int>{10, 10, 10}, std::vector<int>{20, 20, 20}) | 3 |
sessionRooms(std::vector<int>{10, 15}, std::vector<int>{20, 25}) | 2 |
sessionRooms(std::vector<int>{10, 20, 30}, std::vector<int>{15, 25, 35}) | 1 |
Hint
Sort starts and ends independently. Walk both lists with two pointers; the gap between active starts and ends at each step is the current room count — track the peak.
Reference solution in C++
int sessionRooms(std::vector<int> starts, std::vector<int> ends) {
std::vector<int> s = starts;
std::sort(s.begin(), s.end());
std::vector<int> e = ends;
std::sort(e.begin(), e.end());
int peak = 0, active = 0, j = 0;
for (size_t i = 0; i < s.size(); i++) {
active++;
while (j < (int) e.size() && e[j] <= s[i]) { active--; j++; }
if (active > peak) peak = active;
}
return peak;
}