Each warehouse sends a manifest of item codes already sorted in ascending order. Given manifests, a list of such sorted lists, return one list containing every item code in ascending order.
Examples
Input: manifests = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Input: manifests = [[], [7], []]
Output: [7]
Constraints
0 <= len(manifests) <= 200, total number of codesN <= 10**5- Every inner list is sorted ascending; duplicates across lists are possible.
- Target complexity: O(N log k) where
kis the number of manifests.
Goals
- Merge many sorted lists without re-sorting everything
- Use a heap of (value, list index, position) to pick the next smallest element
- Handle empty inner lists and an empty outer list