☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Shortest Job First

Medium TUF ID 551 A2Z

Java source ↗ Edit this article ↗

Problem

A CPU has n processes to run. Process i needs bt[i] units of CPU time (its burst time), and every process arrives at time 0. The scheduler is non-preemptive Shortest Job First (SJF): whenever the CPU becomes free, it picks the waiting process with the smallest burst time and runs it to completion. The waiting time of a process is how long it sits in the queue before it starts, which here equals its start time. Return the average waiting time, rounded down to an integer.

Constraints (GfG version): 1 ≤ n ≤ 10^5, 1 ≤ bt[i] ≤ 10^5.

Example 1

bt = [4, 3, 7, 1, 2]
answer = 4

SJF runs the bursts in the order 1, 2, 3, 4, 7. They start at times 0, 1, 3, 6, 10, so the total waiting time is 20 and the average is 20 / 5 = 4.

Example 2

bt = [1, 2, 3, 4]
answer = 2

Start times are 0, 1, 3, 6, total 10, average 2.5, rounded down to 2.

Why SJF at all. Run the processes in some order with bursts b1, b2, ..., bn. Process k waits for everything before it, so the total waiting time is (n-1)·b1 + (n-2)·b2 + ... + 1·b(n-1) + 0·bn: each burst is multiplied by the number of processes queued behind it. To make that sum small, the biggest multipliers must go to the smallest bursts, which is exactly ascending order. Equivalently, if a longer job ever runs immediately before a shorter one, swapping them lowers the shorter job’s wait by more than it raises the longer job’s wait. That exchange argument is why SJF minimises average waiting time when everything arrives together, and it is why this problem sits in the greedy section.

Approach 1: Brute force, simulate the scheduler

Intuition. Do literally what the scheduler does. Keep a clock. At each step, scan all unfinished processes for the one with the smallest burst, record the current clock as its waiting time, advance the clock by its burst, and mark it done. Ties may be broken arbitrarily: equal bursts produce the same multiset of start times whichever goes first.

Algorithm.

  1. clock = 0, totalWait = 0, all processes unfinished.
  2. Repeat n times: find the unfinished process with the smallest burst; add clock to totalWait; add its burst to clock; mark it done.
  3. Return totalWait / n (integer division of non-negative numbers rounds down).
static long bruteForce(int[] bt) {
    int n = bt.length;
    if (n == 0) return 0;
    boolean[] done = new boolean[n];
    long clock = 0, totalWait = 0;
    for (int step = 0; step < n; step++) {
        int pick = -1;
        for (int i = 0; i < n; i++) {
            if (!done[i] && (pick == -1 || bt[i] < bt[pick])) pick = i;
        }
        totalWait += clock;                  // job 'pick' has waited from time 0 until now
        clock += bt[pick];
        done[pick] = true;
    }
    return totalWait / n;
}

Complexity. Time O(n^2): n selections, each scanning n processes. Space O(n) for the done flags. With n = 10^5 that is 10^10 steps, far too slow.

Approach 2: Optimal, sort once

Intuition. The simulation keeps asking “what is the smallest remaining burst?” and the answers, in order, are simply the bursts sorted ascending. So sort once and walk the sorted array with a running clock. Each process waits for the sum of everything before it, which is the clock value when we reach it.

Algorithm.

  1. Copy and sort the burst times.
  2. clock = 0, totalWait = 0. For each burst b in sorted order: totalWait += clock, then clock += b.
  3. Return totalWait / n.
static long optimal(int[] bt) {
    int n = bt.length;
    if (n == 0) return 0;
    int[] sorted = bt.clone();
    Arrays.sort(sorted);
    long clock = 0, totalWait = 0;
    for (int b : sorted) {
        totalWait += clock;
        clock += b;
    }
    return totalWait / n;
}

Dry run on example 1, sorted bursts [1, 2, 3, 4, 7]:

position burst waiting time (clock before) clock after
1 1 0 1
2 2 1 3
3 3 3 6
4 4 6 10
5 7 10 17

Total waiting time 0 + 1 + 3 + 6 + 10 = 20, average 20 / 5 = 4.

Complexity. Time O(n log n) for the sort; the accumulation is O(n). Space O(n) for the sorted copy (or O(1) extra if you may sort the input in place). Since bursts are bounded by 10^5, a counting sort would make this O(n + max burst), but Arrays.sort is already far inside the limits.

The same loop gives the other usual metrics for free: the turnaround time of a process is its waiting time plus its burst, which is the clock after column, and the average turnaround is the average waiting time plus the average burst.

Edge cases and pitfalls