# [LC] 253. Meeting Rooms II

Given an array of meeting time intervals `intervals` where `intervals[i] = [starti, endi]`, return the minimum number of conference rooms required.

Example 1:

```Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
```

Example 2:

```Input: intervals = [[7,10],[2,4]]
Output: 1
```

Constraints:

• `1 <= intervals.length <= 104`
• `0 <= starti < endi <= 106`

## Approach

It is another problem I spent about 5 hours until midnight and I finally realized I tried to use the wrong approach.

In here, I only tried to find where is the overlapped position. Since it requires only maximum overlapped interval, I may use the longest one to find max overlaps. However, it has too many cases. Maybe the longest one does not overlap other N-1 cases. Maybe there are all same intervals.

My problem was I treated this problem as a “coordination” problem. I mean, I set x = beginning time and y = finishing time and tried to find overlaps of [x,y] pairs and it brought me a lot of cases! I almost gave up but finally, I got the idea of it.

It was simple. Just sort by beginning/ending time and save into another 1D array/list. Let says A[] has sorted beginning time and B[] has sorted ending time. Then we can get the earliest time from 0 to N in A[] and B[]. If it is from A, then we increase # of rooms. Otherwise, decrease. And check the max # of room for every iteration. Here is my final solution:

``````class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if len(intervals) == 0:
return 0
A = [i for [i,j] in sorted(intervals, key=lambda a: a)]
B = [j for [i,j] in sorted(intervals, key=lambda a: a)]

s = 0
i,j = 0,0
m = 0
while i < len(A) and j < len(B):
if A[i] < B[j]:
s+=1
i+=1
else:
s-=1
j+=1
m = max(m,s)

return m``````

Time/Space Complexity: O(N)

Submission

Runtime: 76 ms, faster than 75.82% of Python3 online submissions for Meeting Rooms II.

Memory Usage: 17.5 MB, less than 68.85% of Python3 online submissions for Meeting Rooms II.