[LeetCode] 253. Meeting Rooms II_Medium tag: Heap

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

 

Ideas:  

1. 先sort intervals,然后将meeting 按照start time 来排列

2. 建一个以end time 为element的min heap

3. 每次对于每个interval, 看start time >= min heap[0](最早结束的meeting), 表明有房间空出来, 那么heapq.heappop(free_rooms)

4. 再heapq.heappush(free_rooms, endtime)

5. 将所有会议都review一遍之后还在heap里面的就是需要的房间的数量

Code

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        free_rooms = []
        for s, e in intervals:
            if free_rooms and s >= free_rooms[0]:
                heapq.heappop(free_rooms)
            heapq.heappush(free_rooms, e)
        return len(free_rooms)

 

上一篇:Java 循环结构 - for, while 及 do...while


下一篇:经典论文系列 | 缩小Anchor-based和Anchor-free检测之间差距的方法:自适应训练样本选择