Single-Core Job Order
A machine with one CPU core receives jobs. Job i is jobs[i] = [arrival, duration]: it becomes available at time arrival and needs duration units of CPU time once started. A started job runs to completion without interruption.
Whenever the core is free, it looks at all jobs that have arrived and not yet run, and starts the one with the shortest duration; ties go to the smaller index. If nothing is waiting, the core stays idle until the next arrival. A job that arrives at the exact moment the core becomes free is available for that choice.
Return the indices of the jobs in the order they are started. Implement the priority queue yourself.
Example 1
Input: jobs = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1] Explanation: At t=1 only job 0 is waiting. At t=3 jobs 1 and 2 wait; 2 is shorter. At t=5 job 3 (length 1) beats job 1.
Example 2
Input: jobs = [[7,10],[7,12],[7,5],[7,4],[7,2]] Output: [4,3,2,0,1] Explanation: All arrive together, so they run shortest first.
Constraints
- 1 <= jobs.length <= 2 * 10^4
- 0 <= arrival <= 10^9
- 1 <= duration <= 10^9
Hint 1
Sort job indices by arrival time and feed them into a min-heap keyed by (duration, index) as time advances.
Hint 2
If the heap is empty, jump the clock forward to the next arrival.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, DevOps Engineer, Site Reliability Engineer, Cloud Engineer, Embedded Systems Engineer, MLOps Engineer
Run checks your code on 2 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.