Run Jobs Shortest-First and Report Each Job's Wait
Solve this ProblemA single processor must run a set of jobs. Job i becomes available at time arrival[i] and needs burst[i] time units. Once a job starts it runs to completion. Whenever the processor becomes free it starts the available job with the smallest burst (ties go to the earlier arrival, then the smaller index); if no job is available it idles until the next one arrives.
A job's wait is the time between its arrival and the moment it starts. Return the wait of every job, in the original input order.
Scanning every job each time the processor frees up works but repeats effort. Sorting the jobs by arrival and keeping the already-arrived jobs in a min-heap ordered by burst hands over the shortest available job in O(log n).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ arrival.length ≤ 30, and burst.length equals arrival.length - ◆
0 ≤ arrival[i] ≤ 100, 1 ≤ burst[i] ≤ 50; job i becomes available at time arrival[i] and needs burst[i] time units on a single processor - ◆
The processor runs one job at a time and never interrupts it (non-preemptive). Whenever it becomes free, it starts the available job with the smallest burst; ties go to the earlier arrival, then to the smaller index - ◆
If no job is available when the processor becomes free, it idles until the next arrival. A job's wait is (its start time) − (its arrival time). Return every job's wait, in input order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan Every Job Each Time the Processor Frees Up
BruteSimulate the processor directly. Each time it becomes free, scan every job: skip the finished ones and any that haven't arrived yet, and among the rest pick the one with the smallest burst (ties to the earlier arrival; the scan goes in index order, so the smaller index wins the final tie). If nothing has arrived yet, jump the clock to the earliest unfinished arrival and scan again. The chosen job's wait is the clock minus its arrival; then advance the clock by its burst. It works, but each of the n selections re-scans all n jobs.
O(n²)O(n)1class Solution {
2 public List<Integer> sjfWaitingTimes(int[] arrival, int[] burst) {
3 int n = arrival.length;
4 boolean[] done = new boolean[n];
5 int[] waiting = new int[n];
6 int time = 0, finished = 0;
7 while (finished < n) {
8 int best = -1;
9 for (int i = 0; i < n; i++) {
10 if (done[i] || arrival[i] > time) continue;
11 if (best == -1 || burst[i] < burst[best]
12 || (burst[i] == burst[best] && arrival[i] < arrival[best])) best = i;
13 }
14 if (best == -1) {
15 int earliest = Integer.MAX_VALUE;
16 for (int i = 0; i < n; i++) {
17 if (!done[i]) earliest = Math.min(earliest, arrival[i]);
18 }
19 time = earliest;
20 continue;
21 }
22 waiting[best] = time - arrival[best];
23 time += burst[best];
24 done[best] = true;
25 finished++;
26 }
27 List<Integer> result = new ArrayList<>();
28 for (int w : waiting) result.add(w);
29 return result;
30 }
31}Optimal — Sort by Arrival, Min-Heap of Ready Jobs
OptimalSort the job indices by arrival once. Keep a min-heap of the jobs that have already arrived and are waiting, ordered by (burst, arrival, index). Each round: if the heap is empty and the next job hasn't arrived, jump the clock to its arrival; then move every job whose arrival is at or before the clock from the sorted list into the heap; pop the heap's top — the shortest available job — record its wait, and advance the clock by its burst. Each job enters and leaves the heap once, so the total is O(n log n).
O(n log n)O(n)1class Solution {
2 public List<Integer> sjfWaitingTimes(int[] arrival, int[] burst) {
3 int n = arrival.length;
4 Integer[] order = new Integer[n];
5 for (int i = 0; i < n; i++) order[i] = i;
6 Arrays.sort(order, (a, b) -> arrival[a] != arrival[b] ? arrival[a] - arrival[b] : a - b);
7 PriorityQueue<Integer> ready = new PriorityQueue<>((a, b) -> {
8 if (burst[a] != burst[b]) return burst[a] - burst[b];
9 if (arrival[a] != arrival[b]) return arrival[a] - arrival[b];
10 return a - b;
11 });
12 int[] waiting = new int[n];
13 int time = 0, pos = 0;
14 for (int done = 0; done < n; done++) {
15 if (ready.isEmpty() && time < arrival[order[pos]]) time = arrival[order[pos]];
16 while (pos < n && arrival[order[pos]] <= time) ready.offer(order[pos++]);
17 int current = ready.poll();
18 waiting[current] = time - arrival[current];
19 time += burst[current];
20 }
21 List<Integer> result = new ArrayList<>();
22 for (int w : waiting) result.add(w);
23 return result;
24 }
25}