13. Assign Tickets by SLA Deadline

Problem

A support-ticket system fields tickets each carrying an SLA deadline; the soonest deadline should always be handled next, regardless of arrival order. Given a stream of tickets and a fixed number of available agents, process tickets in strict deadline order using a min-heap, assigning agents round-robin in the order tickets are handled (not the order they arrived).

tickets is a list of (ticket_id, deadline), NOT pre-sorted. The function returns a list of (ticket_id, agent_index) in handling order: soonest deadline first, ties broken by original input (list) order; agent_index cycles 0..num_agents-1 in that handling order.

Source: src/13_assign_tickets_by_deadline.py

def assign_by_deadline(tickets: list[tuple[str, float]], num_agents: int) -> list[tuple[str, int]]: ...

>>> assign_by_deadline([("a", 5.0), ("b", 1.0), ("c", 3.0)], num_agents=2)
[('b', 0), ('c', 1), ('a', 0)]
>>> assign_by_deadline([("a", 2.0), ("b", 2.0), ("c", 1.0)], num_agents=3)
[('c', 0), ('a', 1), ('b', 2)]

Step-by-Step Approach

1. Build a min-heap keyed on (deadline, original_index, ticket_id). Including original_index both breaks ties deterministically (earliest-arrival-first among equal deadlines) and avoids ever comparing two tuples on ticket_id if deadlines and indices happen to tie (they can't, since index is unique).
2. Heapify the list of all tickets up front in O(n) — you don't need to push one at a time since the whole ticket list is known ahead of time.
3. Pop from the heap repeatedly; each pop gives you the ticket with the globally next-soonest deadline, which is exactly the "handling order."
4. Maintain a running agent counter starting at 0. After handling each ticket, append (ticket_id, agent) to the result and advance agent = (agent + 1) % num_agents.
5. Continue until the heap is empty; return the accumulated result list.
6. Handle the empty-tickets case by returning an empty list directly (heapify on an empty list is a no-op, so this falls out naturally).

The key insight is that "assign agents round-robin in handling order" decouples entirely from "sort by deadline" — you first fully resolve the deadline-priority order via the heap, and only then do a simple modulo counter over that resolved order, rather than trying to interleave the two concerns.

Reference solution

import heapq


def assign_by_deadline(tickets: list[tuple[str, float]], num_agents: int) -> list[tuple[str, int]]:
    # enumerate pairs each ticket with its index; idx breaks deadline ties before ticket_id ever compares
    heap = [(deadline, idx, ticket_id) for idx, (ticket_id, deadline) in enumerate(tickets)]
    # O(n) in-place heap build, cheaper than n individual pushes
    heapq.heapify(heap)
    result: list[tuple[str, int]] = []
    agent = 0
    while heap:
        # O(log n) pop of smallest; _, _ discards deadline/idx
        _, _, ticket_id = heapq.heappop(heap)
        result.append((ticket_id, agent))
        # cycles 0..num_agents-1
        agent = (agent + 1) % num_agents
    return result

Key Functions & Tricks

• heapq.heapify(list) — O(n) in-place heap build, cheaper than pushing each ticket one at a time.
• heapq.heappop(heap) — O(log n) pop of the smallest element; Python's heapq is min-heap only.
• enumerate(tickets) in a list comprehension — pairs each ticket with its original index in one line.
• (deadline, idx, ticket_id) tuple ordering — idx tie-breaks deadlines so ticket_id strings are never compared.
• _, _, ticket_id = heapq.heappop(heap) — underscore convention discards tuple elements you don't need.
• agent = (agent + 1) % num_agents — modulo cycles the round-robin agent index.

How to Recognize This Pattern