将会议时间列表分配给会议室

Question

给定会议时间段列表，我试图将它们分配到会议室（同时使用最少的房间）。它工作得相当好，但它 returns 有时值不正确，我不明白为什么。

from typing import List, Tuple
import heapq

def offer(begin:int, end:int, heap:List[int]) -> int:
    while heap and heap[0] <= begin:
        heapq.heappop(heap)
    heapq.heappush(heap, end)
    return len(heap)


def schedule(times:List[Tuple[int, int]]):
    heap = []
    groups = defaultdict(list)
    for begin, end in sorted(times):
        key = offer(begin, end, heap)
        groups[key].append( (begin, end))
    
    return groups

1) 测试成功：

times = [(12, 13), (12, 15), (17, 20)]
assert schedule(times) == [(1, (12, 13)), (2, (12, 15)), (1, (17, 20))] # works

2) 测试成功：

一个更复杂的案例。

times = [(12,13), (13,15), (17,20), (13,14), (19 , 21), (18, 20), (12,13)] 
assert schedule(vals) == {
    1: [(12, 13), (13,14),(17, 20)],
    2: [(12, 13), (13, 15), (18, 20),],
    3: [(19, 21)],
} # works

3) 不成功

看似简单但失败

times =  [(12, 16), (15,18), (17,20)]
assert schedule(times) == {
    1: [(12, 16), (17,20)],
    2: [(15,18)],
} # error

而是将两个会议分配到明显重叠的第二个房间： defaultdict(list, {1: [(12, 16)], 2: [(15, 18), (17, 20)]})

Answer 1

问题是您没有跟踪当前哪些房间是空闲的。您的 'offer' 代码假定如果有一个房间正在使用（即 len(heap)==1），则它始终是第一个房间。要解决此问题，请跟踪哪些房间空闲：

def offer(begin: int, end: int, heap: List[Tuple[int, int]], free_rooms: List[int]) -> int:
    while heap and heap[0][0] <= begin:
        free_rooms.append(heapq.heappop(heap)[1])
    if not free_rooms:
        some_free_room = len(heap) + 1
    else:
        some_free_room = free_rooms.pop()
    heapq.heappush(heap, (end, some_free_room))
    return some_free_room


def schedule(times: List[Tuple[int, int]]):
    heap = []
    free_rooms = []
    groups = defaultdict(list)
    for begin, end in sorted(times):
        key = offer(begin, end, heap, free_rooms)
        groups[key].append((begin, end))

    return groups

此代码可能仍无法通过其中一些测试。原因是在分配最少的房间时有不止一种安排方式；您正在检查特定分配。如果你还想要我们应该贪婪地使用第一个空闲房间的属性，你将需要另一个堆：

def offer_first_free(begin: int, end: int, heap: List[Tuple[int, int]], free_rooms: List[int]) -> int:
    while heap and heap[0][0] <= begin:
        heapq.heappush(free_rooms, heapq.heappop(heap)[1])
    if not free_rooms:
        first_free_room = len(heap) + 1
    else:
        first_free_room = heapq.heappop(free_rooms)
    heapq.heappush(heap, (end, first_free_room))
    return first_free_room

将会议时间列表分配给会议室

Assigning a list of meeting times to meeting rooms

python

algorithm

heap

1) 测试成功：

2) 测试成功：

3) 不成功