[LC] 253. Meeting Rooms IITech
Given an array of meeting time intervals
intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Input: intervals = [[7,10],[2,4]] Output: 1
1 <= intervals.length <= 104
0 <= starti < endi <= 106
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)
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.