Meeting Rooms II
- 2 min read
- Interval
- LC-Medium
3 years ago
Solution
- Keep track of the number of meetings going on at any time (and haven't ended yet). Your answer will be the maximum number of meetings going on at a time
- Create two arrays, one with start times, one with end times.
- Two pointer problem:
- Have a pointer at start times array and also at end times array
- Whenever the value at pointer in start time is lower than current pointer in end time, it means a meeting has started. Increment
count - Whenever the value in start is greater than or equal value in end, meeting has ended, decrement
count - At all points, keep track of maximum number of concurrent meetings. This is your answer.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
starts = sorted([interval[0] for interval in intervals])
ends = sorted([interval[1] for interval in intervals])
i = j = rooms = ans = 0
while i < len(intervals):
if starts[i] < ends[j]:
i += 1
rooms += 1
else:
j += 1
rooms -= 1
ans = max(ans, rooms)
return ans