LC 253 - Meeting Rooms II

Question

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

Links

Question here and solution here

Solution

concept

The greedy way to solve this problem is separate the start and end of the intervals and sort them separately. We will have one pointer for each array and as we iterate through these 2 arrays:

1. If the start[i] < end[j], this means that we will have a meeting starting, therefore the concurrent overlap +1
2. if start[i] >= end[j], means that one of the meeting ended and one room is released, so overlap -1.

code

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        start = sorted([i[0] for i in intervals])
        end = sorted(i[1] for i in intervals)

        count, ans = 0, 0
        s, e = 0, 0 # pointers
        while s < len(start):
            if start[s] < end[e]:
                count += 1
                s += 1
            else:
                count -= 1
                e += 1
            ans = max(ans, count)
        
        return ans

class Solution:
	"""
	heap solution
	"""
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        min_heap = []

        for interval in intervals:
            if min_heap and min_heap[0] <= interval[0]:
                heapq.heappop(min_heap)
            heapq.heappush(min_heap, interval[1])

        return len(min_heap)

Complexity

time: $O(n \log n)$
space: $O(n)$