#194HardHeaps· K-Way Merge
Merge Sorted Event Feeds
Input format
`feeds`: an array of `k` arrays of integers, each sorted in non-decreasing order.
Output format
A single array containing every timestamp in non-decreasing order.
Examples
Input: feeds = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Taking the smallest unconsumed timestamp each time yields 1, 1, 2, 3, 4, 4, 5, 6.
Input: feeds = []
Output: []
With no feeds the combined timeline is empty.
Input: feeds = [[], [7]]
Output: [7]
An empty feed contributes nothing.
Constraints
- 0 <= feeds.length <= 500
- 0 <= feeds[i].length <= 10^4
- Total number of timestamps <= 10^5
- -10^9 <= timestamp <= 10^9
- Each feed is sorted in non-decreasing order.
Study first
- #heap
- #priority-queue
- #merge
- #divide-and-conquer