567. Single Core Order
A processor with one core receives jobs over time. Job i is given as tasks[i] = [arrival, length]: it becomes available at time arrival and needs the core for length time units, with no interruption once started. At time 0 nothing has arrived yet and the core is idle.
Whenever the core is free, it picks, among the jobs that have already arrived and are not yet run, the one with the smallest length; if several have the same length, it picks the one with the smallest index. If no job is waiting, the core stays idle until the next arrival, then applies the same rule. A job that finishes at time t lets the core choose again at time t, counting jobs that arrived at or before t.
Return the indices of the jobs in the order the core runs them. Expected cost is O(n log n) time and O(n) space.
Example 1
- Input:
- tasks = [[1,4],[3,2],[2,1]]
- Output:
- [0,2,1]
- Explanation:
Job 0 runs from time 1 to 5; by then jobs 1 and 2 are both waiting and job 2 is shorter, so the order is 0, 2, 1.
Example 2
- Input:
- tasks = [[5,2],[5,2],[5,2]]
- Output:
- [0,1,2]
- Explanation:
All jobs arrive together with equal length, so the smaller index goes first: 0, 1, 2.
Example 3
- Input:
- tasks = [[1,1],[10,3],[2,1]]
- Output:
- [0,2,1]
- Explanation:
Jobs 0 and 2 run back to back, then the core idles until job 1 arrives at time 10.
Constraints
1 ≤ tasks.length ≤ 100000tasks[i].length == 21 ≤ arrival, length ≤ 109- Finish times can exceed 32 bits; use 64-bit arithmetic for the clock.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)