Stitching the station logs

A thousand mountain weather stations each write a log in minute order, months long. The control room wants the first hundred rows of the merged timeline.

The problem

Station s writes rows of (minute, temperature), where minute counts from midnight on the day the station was installed. Within one station the minutes strictly increase, and a station never writes two rows for the same minute. Across stations, minutes repeat freely — a cold front hits several ridges at once.

The control room asks for the first n rows of the combined timeline, oldest first. When two stations wrote at the same minute, the lower station number is published first, so that a replay is reproducible. Some stations are newly installed and have written nothing yet; those must not break the merge. If the logs hold fewer than n rows in total, publish all of them.

Input. logs — a list of station logs, log s being a list of (minute, temperature) pairs in increasing minute order. n — how many merged rows are wanted.

Output. The first n rows of the merged timeline, as a list of pairs.

Example.

logs = [[(0, -3), (15, -1), (30, 2)],
        [(5, 4), (15, 5)],
        [(10, 0)]]
n = 4     ->  [(0, -3), (5, 4), (10, 0), (15, -1)]

Minute 15 appears in stations 0 and 1, so station 0 publishes first; the merge then stops, having never looked at minute 30.

A second example, asking for more rows than exist, and with an idle station:

n = 10    ->  [(0, -3), (5, 4), (10, 0), (15, -1), (15, 5), (30, 2)]

logs = [[], [(4, 11)], []], n = 3   ->  [(4, 11)]

Constraints.

• 0 <= len(logs) <= 10^3
• each log holds up to 10^6 rows; a log may be empty
• 0 <= minute <= 10^9, -60 <= temperature <= 60
• 0 <= n <= 10^6

Hints

Approach

Brute force

Concatenate every log and sort by (minute, station). With N rows in total that is O(N log N) time and O(N) memory — a thousand stations of a million rows each means a billion rows read and held to answer a question about the first hundred.

The insight

The next row is always the oldest unpublished row of some station, so a heap holding one row per station — k entries, never more — yields the timeline a row at a time and can stop as soon as n rows are out.

Each log is in minute order, so everything behind a station's current row is later than it. The oldest unpublished row is therefore among the k candidates, which is the precondition: within-stream ordering. The heap cannot grow past k because each pop pushes back at most one row, from the station just popped.

Algorithm

1. If n is zero, publish nothing.
2. For each station with a non-empty log, push (minute, station, 0); heapify.
3. Pop the smallest triple and publish logs[station][pos].
4. If the station has a row at pos + 1, push that row's minute with the same station and the new position.
5. Stop when the heap empties or n rows have been published.

Complexity

Time O(k + n log k) — a linear build over the stations, then n pops and pushes of log k each, independent of how long the logs are. Space O(k): one triple per station.

Solution

"""Stitching the station logs — k-way merge whose heap never holds more than k rows."""

import heapq


def solve(logs, n):
    if n <= 0:
        return []

    # Invariant: the heap holds one row per station that still has readings — the
    # oldest reading that station has not published. The station id sits in the key,
    # so equal minutes come out lowest-station-first.
    frontier = [(log[0][0], station, 0) for station, log in enumerate(logs) if log]
    heapq.heapify(frontier)

    timeline = []
    while frontier and len(timeline) < n:
        minute, station, pos = heapq.heappop(frontier)
        timeline.append(logs[station][pos])
        if pos + 1 < len(logs[station]):
            heapq.heappush(frontier, (logs[station][pos + 1][0], station, pos + 1))
    return timeline

TESTS = [
    (([[(0, -3), (15, -1), (30, 2)], [(5, 4), (15, 5)], [(10, 0)]], 4),
     [(0, -3), (5, 4), (10, 0), (15, -1)]),
    (([[(0, -3), (15, -1), (30, 2)], [(5, 4), (15, 5)], [(10, 0)]], 10),
     [(0, -3), (5, 4), (10, 0), (15, -1), (15, 5), (30, 2)]),
    (([[(7, 1)], [(7, 2)], [(7, 3)]], 2), [(7, 1), (7, 2)]),
    (([[], [(4, 11)], []], 3), [(4, 11)]),
    (([], 5), []),
    (([[(0, 0)]], 0), []),
]

Pitfalls

• Putting the row itself in the heap instead of the position. Pairs compare fine, but ties then break on temperature, not station number. If station 0's minute-15 reading were 5 and station 1's were -1, the merge would publish station 1 first, against the stated rule.
• Advancing with a slice, logs[s] = logs[s][1:]. Each pop then copies up to a million rows, turning O(n log k) into work proportional to the whole archive — the one thing the early stop was meant to avoid.
• Seeding the heap with logs[s][0] for every station. The idle stations in the second example raise IndexError before a single row is published.

Variants

• The card catalogue merge — the same frontier drained to the end, over chains that must be walked by pointer rather than indexed.
• Top-k and two heaps — the lesson behind the size-k frontier, and where else it pays.