Heap Entries as (Priority, Tiebreak, Payload)

core

Implement run_jobs(jobs): jobs is a list of (priority, payload) pairs in arrival order, where payload is a dict like {'name': 'build'}. Execute the jobs lowest priority first, breaking priority ties by arrival order, and return the list of payload['name'] values in execution order.

The drill is the shape of the heap entry. heapq has no key= parameter: entries are ordered by plain tuple comparison, which walks the tuples left to right and stops at the first unequal slot. Push a three-slot entry (priority, i, payload) with the arrival index i in the middle. The index is unique, so comparison always stops at slot two or earlier: equal priorities pop in arrival order for free, and the payload is never compared at all.

Push (priority, payload) instead and the trap springs the moment two priorities tie: tuple comparison falls through to the payloads, dicts do not support <, and the push dies with TypeError: '<' not supported between instances of 'dict'. The same crash hits any object payload without __lt__; linked-list nodes in a k-way merge are the classic case. Payloads that happen to be comparable (strings, ints) are the sneakier version: nothing crashes, ties just break by payload contents instead of arrival order and the bug ships silently.

Pop with the same shape: priority, i, payload = heapq.heappop(heap) unpacks all three slots, and the middle one is deliberately thrown away.

Example: jobs [(2, {'name': 'a'}), (1, {'name': 'b'}), (2, {'name': 'c'})] return ['b', 'a', 'c']. Both priority-2 jobs carry indices 0 and 2, so a (index 0) pops before c (index 2) without their payloads ever being compared.

Input format: each test in tests/*.in is laid out as:

Line 1: n, the number of jobs.
Next n lines: priority name, one job per line in arrival order; each line becomes the pair (priority, {'name': name}).

Test 03.in reads:

5
7 e
7 d
7 c
7 b
7 a

This is the all-ties edge case: five jobs share priority 7, so they must execute in arrival order e d c b a, which only happens when the payloads are never compared.

Where you'll use it:

✦ Solution & editorial unlock with the pass.