Merge K Sorted Data Streams with Variable Weights
You are given multiple sorted arrays of integers representing real-time data streams. Each stream also has a weight associated with it. Your task is to merge all streams into a single sorted stream. Whenever there are multiple identical minimum values available across the streams, you must resolve ties by picking the value from the stream with the highest weight. If both the value and the stream weight are identical, pick the stream with the smaller stream index. Implement a function that returns the merged array.
[ "[[1, 4, 7], [2, 5, 8], [3, 6, 9]]", "[10, 20, 15]" ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
Explanation. Elements are merged in sorted order. Stream 1 has weight 10, Stream 2 has weight 20, Stream 3 has weight 15.
[ "[[5, 10], [5, 12], [5, 8]]", "[1, 3, 2]" ]
[ 5, 5, 5, 8, 10, 12 ]
Explanation. All three streams have the minimum value 5 at the front. Stream index 1 has weight 3 (highest), so its 5 is picked first. Then Stream 2 with weight 2, then Stream 0 with weight 1.
Follow-up: How would your solution change if the streams were infinite generators instead of pre-allocated arrays, and you needed to consume values lazily?
Number of streams is between 1 and 100,000. Total number of elements across all streams does not exceed 200,000. Each stream is already sorted in non-decreasing order. Stream weights are integers between 1 and 10,000.