AlgoViz
HomeGreedy

Shortest Job First

Medium

Run the shortest burst first

Problem

Given CPU burst times, compute the average waiting time under Shortest-Job-First scheduling (run the shortest available job first).

In simple words

Run the shortest jobs first so short tasks don't pile up behind long ones, minimising average wait.

The idea

Sorting the jobs by burst time minimises the average waiting time, because a short job placed first delays everyone by very little while a long one delays everyone by a lot. Accumulate the running total to get each job's wait.

The trick

  • Sort ascending by burst time.
  • Waiting time for a job is the sum of all bursts before it.
  • Optimal for average wait, but can starve long jobs.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

4
3
7
1
2
0
1
2
3
4

Step 1 of 2. Here's the example — [4,3,7,1,2] Values: 4, 3, 7, 1, 2.

1/2
Optimal
timeO(n log n)spaceO(1)
1sort(bursts)2wait=0; total=03for b in bursts:4  total+=wait; wait+=b5return total/n

Input

array
[4, 3, 7, 1, 2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
burst = [4, 3, 7, 1, 2]
Output:
4.0
Explanation:
Serve shortest jobs first → average wait 4.0.

Example 2

Input:
burst = [1, 2, 3]
Output:
1.33
Explanation:
Average waiting time 1.0.

Example 3

Input:
burst = [5]
Output:
0.0
Explanation:
One job waits 0.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.