Scheduling with heaps

To find the fewest rooms that a set of meetings needs, the problem often called meeting rooms II, sort the meetings by start time and keep a min-heap of the end times of the rooms in use. When a meeting starts, only the room that frees up first matters: if it has already emptied, the meeting takes it; otherwise every room is busy and a new one opens. That is O(n log n) for n meetings. A heap decides other schedules the same way, such as a printer that always runs the shortest waiting job. Both problems follow, here with exam halls, with their brute force.

Two scheduling problems

• [(540, 660), (600, 720), (660, 780), (720, 840), (610, 640)] needs 3 halls: at minute 610 three exams run at once.
• [(0, 30), (30, 60), (60, 90)] needs 1 hall, because each exam ends as the next one starts.

For the jobs [(0, 5), (1, 2), (2, 1), (3, 3), (20, 1)], as (arrival, duration), the order is 0, 2, 1, 3, 4: job 0 runs until minute 5, then the shortest of the three waiting jobs, job 2, and the printer idles from 11 to 20.

The brute force, and why it fails at these sizes

For problem A, the most exams running at one moment is the answer, and that peak happens at some exam’s start, so count the exams that run at each start: n² = 4 × 10¹⁰ checks at 200,000 exams. For problem B, scan every job at every decision for the shortest waiting one: n² = 10¹⁰ looks at 100,000 jobs.

# Both problems the slow way, with the work counted: halls by counting the exams that run at each exam's start, and
# the printer by scanning every job at every decision.


def halls_by_counting(exams):
    """Problem A: the most exams running at one moment, checked at every start. Exams are half-open [start, end)."""
    best, checks = 0, 0
    for s, _ in exams:
        running = 0
        for a, b in exams:
            checks += 1
            running += a <= s < b
        best = max(best, running)
    return best, checks


def order_by_scanning(jobs):
    """Problem B: at each decision, scan every unprinted job for the shortest one that has arrived."""
    done, order, t, looks = [False] * len(jobs), [], 0, 0
    while len(order) < len(jobs):
        pick = None
        for i, (arrival, duration) in enumerate(jobs):
            looks += 1
            if not done[i] and arrival <= t and (pick is None or duration < jobs[pick][1]):
                pick = i  # strict <: the lower index stays on a tie
        if pick is None:  # nothing waiting: idle until the next arrival
            t = min(a for i, (a, _) in enumerate(jobs) if not done[i])
            continue
        done[pick] = True
        order.append(pick)
        t += jobs[pick][1]
    return order, looks


print("A:", *halls_by_counting([(540, 660), (600, 720), (660, 780), (720, 840), (610, 640)]), "checks")
print("A:", *halls_by_counting([(0, 30), (30, 60), (60, 90)]), "checks")
print("B:", *order_by_scanning([(0, 5), (1, 2), (2, 1), (3, 3), (20, 1)]), "looks")
n = 200_000
print(f"A at {n:,} exams: n * n = {n * n:,} checks")
n = 100_000
print(f"B at {n:,} jobs: n * n = {n * n:,} looks, one scan of every job per job printed")

A: 3 25 checks
A: 1 9 checks
B: [0, 2, 1, 3, 4] 30 looks
A at 200,000 exams: n * n = 40,000,000,000 checks
B at 100,000 jobs: n * n = 10,000,000,000 looks, one scan of every job per job printed

What to notice

• When an exam starts, only the hall that frees first matters. If even that one is still busy, every hall is.
• When the printer finishes a job, only the shortest waiting job matters. The others wait for later decisions.

Both problems repeatedly ask for the smallest item of a collection that grows and shrinks: the earliest end time among the halls in use, the shortest duration among the waiting jobs. That is a min-heap’s job.

Halls, step by step: a heap of end times Pro: opens with a Pro, Premium or Ultimate pass