# [LC] 253. Meeting Rooms II

TechGiven an array of meeting time intervals `intervals`

where `intervals[i] = [start`

, return _{i}, end_{i}]*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 <= 10`

^{4}`0 <= start`

_{i}< end_{i}<= 10^{6}

## 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[0])]
B = [j for [i,j] in sorted(intervals, key=lambda a: a[1])]
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.