Sorting office bins

The night belt at a sorting office carries parcels past in the order they were unloaded. Each is stamped with a route number, and the loading bay wants them handed over route by route.

The problem

Every parcel carries a label and a route number. Routes run from 0 to routes - 1, the office knows routes in advance — it is printed on the wall — and a route may receive no parcels at all.

Hand the parcels over ordered by route number, smallest first. Within a route they keep belt order: the earliest parcel off the belt is loaded nearest the van door and goes out first, so reordering two parcels on one route is a fault. The belt is long — a busy night is a million parcels — and the routes are few next to it.

Input. parcels — a list of (label, route) pairs in belt order. routes — the number of routes; every route satisfies 0 <= route < routes.

Output. A list of labels, ordered by route, ties in belt order.

Example.

parcels = [("P1", 3), ("P2", 0), ("P3", 3), ("P4", 1), ("P5", 0)], routes = 4
  ->  ["P2", "P5", "P4", "P1", "P3"]

Route 0 takes P2 then P5 — belt order, not label order. Route 1 takes P4, route 2 takes nothing, route 3 takes P1 then P3.

A second example, where the route numbers run far ahead of the parcel count and one route holds everything:

parcels = [("A", 7), ("B", 0)], routes = 8      ->  ["B", "A"]
parcels = [("A", 2), ("B", 2), ("C", 2)], routes = 5  ->  ["A", "B", "C"]

An empty belt hands over an empty list.

Constraints.

• 0 <= len(parcels) <= 10^6
• 1 <= routes <= 10^6
• 0 <= route < routes

Hints

Approach

Brute force

For each route from 0 upward, scan the whole belt and take the parcels stamped with it. Belt order survives for free and no comparison is made, but it costs O(n · routes) — 10^9 reads for a million parcels over a thousand routes.

The insight

The route number is not something to compare, it is an address: one pass tallies how many parcels each route holds, a prefix sum turns those tallies into the first output slot of each route's block, and a second pass drops every parcel straight into its slot.

This is legal only because the keys are integers in a range known in advance — the precondition worth naming, and what buys an O(n + k) sort past the n log n floor comparison sorts cannot cross. Belt order survives because the second pass walks forward and each route's cursor only moves right, so an earlier parcel claims a lower slot than a later one on the same route.

Algorithm

1. Tally counts[route] over the belt.
2. Sweep the tallies into offsets: offset[r] is the total of every count below r, which is where route r's block starts.
3. Make an output list as long as the belt.
4. For each parcel in belt order, write its label at offset[route], then add one to that offset.
5. Return the output list.

Complexity

Time O(n + k) for n parcels and k routes — three linear passes, no comparisons. Space O(n + k) for the output and the tallies.

Against a comparison sort's n log n, this wins while k stays within a small multiple of n: a million parcels over a thousand routes is a couple of million steps against about twenty million. It loses when the key range explodes — sorting by a 32-bit tracking number would allocate four billion tallies to hold a million values.

Solution

"""Sorting office bins — stable counting sort by route with prefix-sum offsets."""


def solve(parcels, routes):
    counts = [0] * routes
    for _, route in parcels:
        counts[route] += 1

    # invariant: offsets[r] is the number of parcels on routes below r, which is
    # the first output slot of route r's block.
    offsets = [0] * routes
    running = 0
    for route in range(routes):
        offsets[route] = running
        running += counts[route]

    handover = [None] * len(parcels)
    for label, route in parcels:
        # Walking the belt forward and stepping the cursor right keeps two
        # parcels on one route in the order they arrived.
        handover[offsets[route]] = label
        offsets[route] += 1
    return handover

TESTS = [
    (([("P1", 3), ("P2", 0), ("P3", 3), ("P4", 1), ("P5", 0)], 4),
     ["P2", "P5", "P4", "P1", "P3"]),
    (([("A", 7), ("B", 0)], 8), ["B", "A"]),
    (([("A", 2), ("B", 2), ("C", 2)], 5), ["A", "B", "C"]),
    (([], 4), []),
    (([("solo", 0)], 1), ["solo"]),
    (([("A", 3), ("B", 2), ("C", 3), ("D", 0)], 4), ["D", "B", "A", "C"]),
]

Pitfalls

• Placing parcels with the raw tallies instead of the prefix sums. Every parcel on route 3 writes to slot 3, so a route's parcels overwrite each other and most of the output stays empty.
• Walking the belt backwards with block-start offsets. The backward pass uses each block's end and steps left; mixing the directions reverses belt order within a route, loading P5 ahead of P2.
• Sizing the tally array from the parcels. max(route) + 1 breaks on an empty belt, and len(parcels) raises an index error the moment a two-parcel night carries route 7. The wall gives you routes.

Variants

• Kiln slots — the same bounded range, tallying a timeline instead of a set of keys.
• Order as a key — what stability promises you when two elements answer the key identically.