Shortest-Job Server Order
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
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
| tasks | result |
|---|---|
[[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
-
tasks.length, eachtasks[i]has length 2 -
enqueueTime,processingTime - Times can exceed the 32-bit integer range.
Expected complexity
- Time
- O(N log N)
- Space
- O(N)
Examples
| tasks | Expected |
|---|---|
[[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 . 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. ; the clock can reach about , so use 64-bit integers.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 282 ms | estimated |
| C++ (GCC, gnu++23) | 282 ms | derived |
| Python 3.13 | 1130 ms | derived |
| Java 25 | 2078 ms | derived |
| Kotlin 2.4 (JVM) | 1564 ms | estimated |
| C# 14 (.NET 10) | 1564 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |