Skip to the code
cf.
+50 XP

#751 Priority Fetch Queue

hard

A browser-like resource loader runs at most limit fetches at once. Each request is [arrival, priority, duration]: it becomes available at time arrival, and once started it takes duration ms.

Whenever a slot is free and requests are waiting, the loader starts the waiting request with the highest priority; ties go to the earlier arrival, then to the smaller index. At any moment, finished fetches free their slots first, then newly arrived requests join the waiting list, then free slots are filled.

Write startTimes(requests, limit) that returns the time each request starts, in index order.

Example 1

Input: requests = [[0,1,100],[10,1,50],[20,5,30]], limit = 1
Output: [0,130,100]

At 100 both waiting requests are available, and request 2 has the higher priority.

Example 2

Input: requests = [[0,0,10],[0,0,10],[0,9,10]], limit = 2
Output: [0,10,0]

At time 0 two slots are free; request 2 (priority 9) and request 0 (earliest index) start.

Constraints

  • 0 <= requests.length <= 10^5
  • 0 <= arrival <= 10^9, 0 <= priority <= 100, 1 <= duration <= 10^4
  • 1 <= limit <= 100
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).