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 \le intervals.length \le 10^4$
$0 \le start_i < end_i \le 10^6$

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(s for s, e in intervals)
        ends = sorted(e for s, e in intervals)

        rooms = 0
        end_ptr = 0

        for start in starts:
            if start < ends[end_ptr]:
                rooms += 1      # 没空房，新开一间
            else:
                end_ptr += 1    # 有一场结束了，复用

        return rooms

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(s for s, e in intervals)
        ends = sorted(e for s, e in intervals)

        rooms = 0
        end_ptr = 0

        for start in starts:
            if start < ends[end_ptr]:
                rooms += 1      # 没空房，新开一间
            else:
                end_ptr += 1    # 有一场结束了，复用

        return rooms

Python

这个题的解法很容易懂，但是我想不通的是为什么可以把开始时间和结束时间分开排序，会议过程真的没有意义吗？这样计算会不会产生重复？但是当用这种时间轴的图显示一下就可以发现，过程确实没关系。我们只需要知道会议开始的时候有没有别的会议结束就可以了，如果有，我们就有可以复用的会议室。

因此具体做法就是

把开始时间和结束时间分别从小到大排序
循环开始时间，
1. 如果开始时间小于结束时间，说明会议开始的时候前面有别的会议没结束，我们就rooms+=1
2. 如果开始时间大于等于结束时间，说明会议开始的时候有会议结束，可以复用rooms就不需要+=1 直接结束时间的指针后移，找到下一个会议结束时间
最后rooms就是我们得到的需要的最小会议室数量。

虽然这么理解看上去没问题，但是算法题最重要的是你的抽象是否正确。所以我又去看了leetcode，他给出了一个非常容易理解的正向思路。

首先我们处理会议室的时候肯定是先处理最早开始的那场然后再处理后开始的。所以先按照start时间把数组排序。假设我们现在有了这样一个数组：

(1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30)

当我们第一场会议开始的时候我们需要记录它的结束时间

end = [10]
length  = 1

第二场会议开始的时候我们看end里面最小数是10，2<10 所以我们需要单开

end = [10,7]
length = 2

第三场会议开始的时候end里面最小数值是7，3<7，所以length继续增加

end = [10,7,19]
length = 3

以此类推第四场会议开始时间是8， 8>7所以我们可以复用一个会议室，同时把7移掉

end = [10, 12, 19]
length = 3

第五场会议开始时间是10， 10 >=10所以我们可以再次复用一个会议室，同时把10移掉

end = [20, 12, 19]
length = 3

第六场会议开始时间是11， 11<12所以我们需要再多加一个实验室

最后length = 4

这样我们可以用优先队列来计算这个问题

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # The heap initialization
        free_rooms = []

        # Sort the meetings in increasing order of their start time.
        intervals.sort(key= lambda x: x[0])

        # Add the first meeting. We have to give a new room to the first meeting.
        heapq.heappush(free_rooms, intervals[0][1])

        # For all the remaining meeting rooms
        for i in intervals[1:]:

            # If the room due to free up the earliest is free, assign that room to this meeting.
            if free_rooms[0] <= i[0]:
                heapq.heappop(free_rooms)

            # If a new room is to be assigned, then also we add to the heap,
            # If an old room is allocated, then also we have to add to the heap with updated end time.
            heapq.heappush(free_rooms, i[1])

        # The size of the heap tells us the minimum rooms required for all the meetings.
        return len(free_rooms)

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # The heap initialization
        free_rooms = []

        # Sort the meetings in increasing order of their start time.
        intervals.sort(key= lambda x: x[0])

        # Add the first meeting. We have to give a new room to the first meeting.
        heapq.heappush(free_rooms, intervals[0][1])

        # For all the remaining meeting rooms
        for i in intervals[1:]:

            # If the room due to free up the earliest is free, assign that room to this meeting.
            if free_rooms[0] <= i[0]:
                heapq.heappop(free_rooms)

            # If a new room is to be assigned, then also we add to the heap,
            # If an old room is allocated, then also we have to add to the heap with updated end time.
            heapq.heappush(free_rooms, i[1])

        # The size of the heap tells us the minimum rooms required for all the meetings.
        return len(free_rooms)