Scheduling with heaps

Many interview problems simulate time: meetings that need rooms, tasks that arrive and must run on a CPU, jobs with cooldowns or deadlines. At each moment you need one answer, such as 'which room frees up first?' or 'which ready task should run next?'. A heap keyed by that quantity answers it at the top.

The usual recipe is: sort events by time, sweep through them, and keep a heap of active or ready items. Which key you put in the heap (end time, duration, count, deadline) is the whole design decision.

1. 1Identify the events and sort them by time (start times, arrival times).
2. 2Decide what the heap holds and its key: end times of busy rooms (min-heap), ready tasks by duration then index (min-heap), remaining counts of task types (max-heap).
3. 3Sweep: before handling an event, release or add everything that has become due up to the current time (for example, pop rooms whose meeting ended, or push tasks that have arrived).
4. 4Make the decision from the heap top: reuse the earliest-free room, run the shortest ready task, pick the most frequent remaining letter.
5. 5If nothing is ready, jump the clock forward to the next event instead of stepping one time unit at a time.
6. 6The answer is often a property of the heap (its maximum size = rooms needed) or the order of pops.

import heapq

def min_meeting_rooms(intervals):
    intervals.sort()                       # by start time
    ends = []                              # min-heap: end times of rooms in use
    for start, end in intervals:
        if ends and ends[0] <= start:      # earliest-ending room is free again
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)      # every room busy: open a new one
    return len(ends)

def cpu_order(tasks):                      # tasks[i] = (enqueue_time, duration)
    order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
    ready, result, time, i = [], [], 0, 0
    while len(result) < len(tasks):
        if not ready and time < tasks[order[i]][0]:
            time = tasks[order[i]][0]      # CPU idle: jump to the next arrival
        while i < len(order) and tasks[order[i]][0] <= time:
            j = order[i]
            heapq.heappush(ready, (tasks[j][1], j))   # shortest job, then lowest index
            i += 1
        duration, j = heapq.heappop(ready)
        time += duration
        result.append(j)
    return result

min_meeting_rooms keeps the end times of rooms in use; if the earliest one has ended by the next start it is reused, otherwise a new room is opened, so the final heap size is the rooms needed. cpu_order sorts task indices by arrival, pushes arrived tasks keyed by (duration, index), jumps the clock when the CPU would be idle, and always runs the shortest ready task. Both run in O(n log n).

Cost: Typically O(n log n): sorting plus one push and one pop per item. Space O(n) for the heap in the worst case.