Merge Sorted Streams / Top-K

Problem

Merge k sorted event streams into one globally ordered stream (by timestamp), then return the top-k events by a score. Each stream is individually sorted and may be very long or unbounded.

Input / Output

• Input: k streams of events, each sorted by timestamp; a score function; an integer k for the top-k.
• Output: the merged ordered stream, and the top-k events by score.

Constraints

• k (the number of streams) can be large.
• Streams may not fit in memory, so you can only hold a bounded amount of state at once.

Example

k streams of timestamped events -> merged ordered; top 10 by value