Scheduling / meeting rooms (Intervals Sub-pattern)
Count how many intervals are active at the same moment, or check that a new one doesn't clash. Sweep start and end events in time order, or keep a min-heap of end times.
- ›
"can a person attend all meetings?"
- ›
"book an event if it doesn't overlap"
- ›
"minimum number of rooms / platforms"
- ›
"does the car ever carry more than capacity?"
Meeting Rooms only checks neighbours after sorting. My Calendar I is online, so keep bookings in a sorted map and check only the two neighbours of the new one. Meeting Rooms II and Minimum Platforms are the same sweep with opposite tie rules: a meeting ending at 10 frees the room for one starting at 10; a train leaving at 10:00 still blocks a train arriving at 10:00. Car Pooling has weights (passengers) and small coordinates, so a difference array is simplest.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Meeting RoomsWalkthroughEasyBasic Anchor·LeetCode #252 Premium
- 2My Calendar IWalkthroughMediumBasic Reinforcement·LeetCode #729
- 3Meeting Rooms IIWalkthroughMediumMedium·LeetCode #253 Premium
- 4Minimum PlatformsWalkthroughMediumPattern Transfer·GeeksforGeeks
- 5Car PoolingWalkthroughMediumInterview-Level·LeetCode #1094
Template
// Meeting Rooms II: most meetings running at the same time. Meetings are [start, end).
int minMeetingRooms(vector<vector<int>>& meetings) {
vector<int> starts, ends;
for (auto& m : meetings) { starts.push_back(m[0]); ends.push_back(m[1]); }
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, best = 0, e = 0;
for (int s : starts) {
while (e < (int)ends.size() && ends[e] <= s) { rooms--; e++; } // free ended rooms first
rooms++; // this meeting takes one
best = max(best, rooms);
}
return best;
}