Merging k sorted lists with a heap

# Both problems the slow way, with the work counted: scanning every log's front for the next registration, and
# trying every reading as the start of a window.
from bisect import bisect_left


def merge_by_scanning(logs):
    """Problem A: look at the front of every log, take the smallest (minute, counter), repeat."""
    fronts = [0] * len(logs)  # fronts[c]: the next unread position of log c
    merged, looks = [], 0
    while True:
        best = None
        for c, log in enumerate(logs):
            looks += 1
            if fronts[c] < len(log) and (best is None or log[fronts[c]] < logs[best][fronts[best]]):
                best = c  # strict <: on a tie the lower counter, seen first, stays
        if best is None:
            return merged, looks  # every log is used up
        merged.append((logs[best][fronts[best]], best))
        fronts[best] += 1


def window_by_trying_starts(sensors):
    """Problem B: every reading as a start; each sensor's first reading at or after it decides the end."""
    best, searches = None, 0
    for start in sorted({t for readings in sensors for t in readings}):
        end = start
        for readings in sensors:
            searches += 1
            i = bisect_left(readings, start)  # the first reading at or after start
            if i == len(readings):
                return best, searches  # nothing from this sensor at or after start, nor after any later start
            end = max(end, readings[i])
        if best is None or end - start < best[1] - best[0]:
            best = (start, end)  # strict <: the earliest start wins a tie
    return best, searches


def show_merge(merged):
    return " ".join(f"{minute}@{c}" for minute, c in merged)


merged, looks = merge_by_scanning([[540, 545, 600], [541, 600], [], [530]])
print("A:", show_merge(merged), f"({looks} looks)")
window, searches = window_by_trying_starts([[3, 11, 19, 27], [8, 14, 25], [1, 17, 30]])
print("B:", list(window), f"({searches} searches)")

# The worst cases at the limits, counted from the loops above rather than run.
k, n = 10_000, 1_000_000
print(f"A at k = {k:,} logs and N = {n:,} entries: k * (N + 1) = {k * (n + 1):,} looks")
k, n = 1_000, 200_000
print(f"B at k = {k:,} sensors and N = {n:,} distinct readings: up to N * k = {n * k:,} binary searches")

A: 530@3 540@0 541@1 545@0 600@0 600@1 (28 looks)
B: [14, 19] (26 searches)
A at k = 10,000 logs and N = 1,000,000 entries: k * (N + 1) = 10,000,010,000 looks
B at k = 1,000 sensors and N = 200,000 distinct readings: up to N * k = 200,000,000 binary searches