Funcia
Lv.2heappriority-queuesimulationsorting

Shortest-Job Server Order

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

NN jobs arrive at a single server. Job i is tasks[i] = [enqueueTime, processingTime]: it becomes available at time enqueueTime and needs processingTime to finish. The server runs one job at a time:

  • if it is idle and no job is available, it waits for the next arrival;
  • if it is idle and jobs are available, it picks the one with the shortest processing time, breaking ties by smaller index;
  • a started job runs to completion, and the next job can be chosen the moment it finishes.

Return the job indices in the order the server processes them.

Examples

tasksresult
[[1, 2], [2, 4], [3, 2], [4, 1]][0, 2, 3, 1]
[[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]][4, 3, 2, 0, 1]
[[5, 2], [1, 3]][1, 0]

Example 1 — Job 0 runs 1–3; then jobs 1 (4) and 2 (2) are waiting, so 2 runs 3–5; by then job 3 (1) has arrived and runs before 1.

Example 2 — Everything arrives at time 7, so jobs run from shortest to longest.

Example 3 — Job 1 arrives first and runs 1–4; job 0 arrives at 5.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(tasks: int[][]) → int[]

Constraints

  • 1≤N=1 \le N = tasks.length ≤200,000\le 200{,}000, each tasks[i] has length 2
  • 1≤1 \le enqueueTime, processingTime ≤109\le 10^9
  • Times can exceed the 32-bit integer range.

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

tasksExpected
[[1,2],[2,4],[3,2],[4,1]][0,2,3,1]
[[7,10],[7,12],[7,5],[7,4],[7,2]][4,3,2,0,1]
[[5,2],[1,3]][1,0]

Hint

Hint

Scanning every unprocessed job each time the server frees up is O(N2)O(N^2). Sort jobs by arrival, push arrived jobs into a min-heap keyed by (processingTime, index), jump the clock to the next arrival when the heap is empty, otherwise pop and add the processing time. O(Nlog⁡N)O(N \log N); the clock can reach about 2×10142 \times 10^{14}, so use 64-bit integers.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)282 msestimated
C++ (GCC, gnu++23)282 msderived
Python 3.131130 msderived
Java 252078 msderived
Kotlin 2.4 (JVM)1564 msestimated
C# 14 (.NET 10)1564 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.