[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[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.