The card catalogue merge

A closing bookshop chain sends head office one chain of index cards per shop, each chain already in date order. Only one card per shop can ever be next.

The problem

Every shop kept its stock as a thread of index cards: one card per book, carrying the publication year, each card pointing at the next. Within a shop the years never decrease. Head office wants a single thread holding every card from every shop, still in non-decreasing year order, to print the auction catalogue straight off.

Shops that emptied their shelves hand over nothing, and a region with no shops left hands over no threads. Both must survive the merge. Duplicate years are ordinary: three shops each holding a 1962 reprint means three cards, and all three appear in the result.

Input. shops — a list of threads. Thread s is given as a list of publication years in non-decreasing order, and is built into a chain of cards before the merge starts.

Output. One list of years, non-decreasing, holding every card from every thread.

Example.

shops = [[1998, 2003, 2011], [1999, 2003], [1994, 2020]]
  ->  [1994, 1998, 1999, 2003, 2003, 2011, 2020]

Both 2003 cards appear, and the 2020 card waits behind 2011 even though its own thread has nothing in front of it.

A second example, where two shops have nothing to hand over:

shops = [[1962, 1962], [], [1962]]   ->  [1962, 1962, 1962]
shops = []                           ->  []

An empty thread contributes no card, and must not be allowed to seed the merge.

Constraints.

• 0 <= len(shops) <= 10^4
• total cards across all threads <= 10^5
• 1500 <= year <= 2030
• each thread is individually non-decreasing; threads may be empty

Hints

Approach

Brute force

Fold one thread at a time into a growing result. The first merge walks 2n cards, the second 3n, the k-th (k+1)n — about k times the total card count. With 100 shops of 1000 cards that is five million comparisons, nearly all of them re-walking cards already in place.

The insight

Only k cards can ever be next — the front card of each thread — so the merge needs the smallest of k things, which a min-heap hands over in log k.

Each thread is sorted, so every card behind a shop's front card carries a year at least as late. The earliest unfiled card anywhere is therefore one of the k fronts. That per-thread sortedness is the precondition: without it a card buried mid-thread could be the earliest, and the heap root would be wrong.

Algorithm

1. Thread each shop's years into a chain of cards; skip shops with none.
2. Push (year, shop index, card) for each first card, then heapify.
3. Pop the smallest triple and append its year to the result.
4. If that card has a next card, push the next card from the same shop.
5. Stop when the heap is empty.

Complexity

Time O(N log k), where N is the total card count — each card is pushed and popped once, at log k each, because the heap never holds more than one card per shop. Space O(k) for the heap, beyond the cards themselves.

Solution

"""The card catalogue merge — k-way merge of sorted card chains with a min-heap."""

import heapq


class Card:
    """One index card: a publication year, and the next card in that shop's chain."""

    def __init__(self, year, nxt=None):
        self.year = year
        self.next = nxt


def build_chain(years):
    """Thread a list of years into a chain of cards; returns the first card or None."""
    head = None
    for year in reversed(years):
        head = Card(year, head)
    return head


def solve(shops):
    heads = [build_chain(years) for years in shops]

    # Invariant: the heap holds at most one card per shop — the earliest card that
    # shop has not yet handed over. Every card still unfiled is at or behind one of
    # them, so the heap root is the earliest card left anywhere.
    frontier = [(card.year, shop, card) for shop, card in enumerate(heads) if card]
    heapq.heapify(frontier)

    merged = []
    while frontier:
        year, shop, card = heapq.heappop(frontier)
        merged.append(year)
        if card.next is not None:
            # The shop index sits between the year and the card, so ties are broken
            # by an integer and two Card objects are never compared.
            heapq.heappush(frontier, (card.next.year, shop, card.next))
    return merged

TESTS = [
    (([[1998, 2003, 2011], [1999, 2003], [1994, 2020]],),
     [1994, 1998, 1999, 2003, 2003, 2011, 2020]),
    (([[1962, 1962], [], [1962]],), [1962, 1962, 1962]),
    (([],), []),
    (([[], []],), []),
    (([[1977]],), [1977]),
    (([[1901, 1950], [1899], [], [1950, 1951, 1952]],),
     [1899, 1901, 1950, 1950, 1951, 1952]),
]

Pitfalls

• Pushing (year, card) pairs. When two shops front the same year, Python falls through to comparing two card objects and raises a TypeError saying they cannot be ordered — the second example triggers it on the first pop. Put the shop index between year and card, so ties are settled by an integer.
• Seeding the heap from shops[s][0] for every s. The empty thread in the second example raises IndexError before the merge starts.
• Pushing every card up front. The answer is right, but the heap holds 10⁵ entries and the cost is O(N log N) — a sort wearing a heap costume. The gain comes entirely from the heap staying at size k.

Variants

• Stitching the station logs — the same frontier, but the streams are far longer than the answer, so the merge stops early instead of draining.
• The heap invariant — why the root is the minimum and a push costs log k.