Meeting Rooms II

Question

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of rooms required to schedule all meetings without any conflicts.

Example 1:

Input: intervals = [(0,40),(5,10),(15,20)]

Output: 2

Explanation:

• room1: (0,40)
• room2: (5,10),(15,20)

Example 2:

Input: intervals = [(4,9)]

Output: 1

Note:

• (0,8),(8,10) is not considered a conflict at 8

Solution

This is basically a greedy solution where we need try to serve as much meeting within 1 room as possible.

For example, as we go through this array:

(0, 40), (5, 10), (15,20)

We will try to fit the most number of meeting as possible.

First meeting go from 0 — 40. And then we have another meeting at 5 — 10. So we need at least 2 meeting room from 0 — 10.

However, after 10, the second meeting finish and we can re-use the second meeting room for the third meeting room.

So the idea is we sort by the startTime and the endTime.

• For every startTime, we increase the number of room by 1
• For every endTime, we decrease the number of room by 1
• We keep track of the maxRoom

Implentation

class App:
    def minMeetingRooms(self, intervals: List[Interval]) -> int:
        startTime = self.getSortedStartTime(intervals)
        endTime = self.getSortedEndTime(intervals)
        
        currentStart = 0
        currentEnd = 0
        
        maxRoom = 0
        currentRoom = 0
        
        while (currentStart < len(intervals) or currentEnd < len(intervals)):
            if currentStart < len(intervals) and startTime[currentStart] < endTime[currentEnd]:
                currentStart += 1
                currentRoom += 1
            else:
                currentEnd += 1
                currentRoom -= 1
            
            maxRoom = max(currentRoom, maxRoom)
        
        
        return maxRoom
                
    def getSortedStartTime(self, intervals: List[Interval]):
        return sorted([start for start, end in intervals])

    def getSortedEndTime(self, intervals: List[Interval]):
        return sorted([end for start, end in intervals])

Time complexity: $O(nlogn)$
Space complexity: $O(n + n)$