Meeting Rooms II

Intuition

• Keep track of:
  • Minimum end of the intervals you have seen so far
  • Maximum end of the intervals you have seen so far
• On each iteration, if the current interval is dwarfed by the previous one, then another classroom is needed
• If when you reach a new interval, the start time of that new interval is after the start time of the minimum end time, then that class has finished its session, meaning that classroom can be freed, so decrement.
• Do this for every interval you have encountered up until that point
• At the end, return the maximum used classrooms that were necessary at any one point in time

Runtime

• $O(NlogN)$ + $O(NlogN)$ for sorting and popping in a for loop, respectively
  • There are $NlogN$ for pushing and then popping all the N elements
• $O(N)$ space for the heap

Notes

---

References

https://leetcode.com/problems/meeting-rooms-ii/