Assigning a list of meeting times to meeting rooms

Given a list of meetings time blocks I’m trying to allocate them to meeting rooms (while using the least amount of rooms). It works fairly well but it returns the incorrect value sometimes and I can’t figure out why.

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) Successful Test:

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

test-case-1

2) Successful Test:

A more complex case.

case-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) Unsuccessful

case-3

Seems simple enough but fails

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

Instead it allocates two meetings to the second room that clearly overlap: defaultdict(list, {1: [(12, 16)], 2: [(15, 18), (17, 20)]})

Answer

The problem is that you’re not tracking which rooms are currently free. Your code for ‘offer’ assumes that if there is 1 room being used (i.e. len(heap)==1), that it is always the first room. To fix this, track which rooms are free:

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

This code may still fail some of those tests. The reason is that there is more than one way to schedule while allocating the fewest rooms; you are checking against a specific allocation. If you also want the property that we should greedily use the first free room, you’ll need another heap:

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