Recommendation Quorum
A recommendation gateway gets per-source ranked candidate lists from k retrieval services. Each list is already sorted by score descending. The gateway must merge them into one globally sorted feed and emit the first N items as the user scrolls.
Problem
You are given k sorted (descending) lists of integers, where list i has length n_i. Return the first N items of the merged global descending order. Total items across all lists is at least N.
Input
An integer N (1 ≤ N ≤ 10^5), an integer k (1 ≤ k ≤ 10^4), and k lists of integers each in [−10^9, 10^9]. The sum of all n_i is at most 10^6.
Output
A list of N integers — the top N in global descending order. Ties may break in any consistent way.
Constraints
- 1 ≤ N ≤ 100,000
- 1 ≤ k ≤ 10,000
- Each list is already sorted descending
- Total elements ≤ 10^6 — full materialisation is too much memory if you flatten and sort naively
Examples
Example 1
Input
N = 4, lists = [[9, 5, 1], [8, 6, 0], [7, 2]]
Output
[9, 8, 7, 6]
Merge front-of-each: 9, 8, 7, 6 are the four largest.