Merged Price Feed Timeline
MediumHeap ยท Citadel
Merge k price feeds into one timeline. feeds[i] lists [time, delta] events in non-decreasing time order, and the price starts at start.
Process all events in order of time; events with equal time go by feed index, then by position within the feed. Applying a delta adds it to the price, but the price never goes below 0: a delta that would push it under leaves it at 0.
Return [time, price] for each distinct time, in increasing time, where price is the value after every event at that time has been applied.
Example 1
- Input:
- feeds = [[[1, 5], [4, -3]], [[1, -2], [2, 4]]], start = 10
- Output:
- [[1, 13], [2, 17], [4, 14]]
- Explanation
- At time 1 the price goes 10, 15 (feed 0), 13 (feed 1). Times 2 and 4 each have one event.
Example 2
- Input:
- feeds = [[[3, -8]], [[3, 5], [6, 2]]], start = 4
- Output:
- [[3, 5], [6, 7]]
- Explanation
- Feed 0 acts first: 4 - 8 is floored to 0, then feed 1 adds 5.
Example 3
- Input:
- feeds = [[], [[2, 1]], []], start = 0
- Output:
- [[2, 1]]
Constraints
1 <= feeds.length <= 10000 <= feeds[i].length, and the total number of events is at most10^50 <= time <= 10^9, non-decreasing within each feed-10^6 <= delta <= 10^60 <= start <= 10^9