Shortest Job First

You are given an array bt where bt[i] is the burst time (CPU time needed) of process i. Using non-preemptive Shortest Job First (SJF) scheduling, compute the average waiting time across all processes and return its floor (integer part).

A process's waiting time is how long it sits before it starts running — the total burst time of every process scheduled ahead of it.

Hints

· Stuck? Reveal one nudge at a time.

To minimize average waiting time, in what order should the jobs run?

Run the shortest jobs first — a long job early delays everyone behind it.

After sorting, each job's waiting time is the running sum of the burst times before it.

Common doubts

A job of length L adds L to the waiting time of every job after it. Scheduling short jobs first means the large delays are shared by the fewest remaining jobs.

The problem asks for the integer part of the average waiting time, so integer (floor) division of the total by n is exactly what's required.

Yes for large inputs — the total waiting time is a sum of prefix sums and can exceed a 32-bit range, so accumulate it in a 64-bit integer.

Interview follow-ups

· What an interviewer asks next.

Then it becomes SJF with arrivals — at each completion you pick the shortest job that has arrived, typically maintained with a min-heap keyed on burst time.

Turnaround = waiting + burst, so add each job's own burst to its waiting time before averaging.

Fun facts

SJF provably minimizes average waiting time among all non-preemptive schedules — but it needs to know burst times in advance, which real schedulers must estimate.
The 'shortest first' rule is the same intuition behind serving quick tasks before slow ones at any queue or checkout.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: bt = [4, 3, 7, 1, 2]
Output: 4
Sorted bursts 1,2,3,4,7 give waiting times 0,1,3,6,10; average = 20 / 5 = 4.

Example 2

Input: bt = [1, 2, 3]
Output: 1
Waiting times 0,1,3 sum to 4; 4 / 3 floors to 1.

Constraints

- 1 <= bt.length <= 10^4 - 1 <= bt[i] <= 10^5

To make everyone wait as little as possible on average, run the shortest jobs first. A long job scheduled early makes every job behind it wait longer, so pushing it to the back minimizes the total (and hence average) waiting time. Once the order is fixed, the waiting times are just prefix sums.

Prerequisites

Before you start

· Concepts used directly in the solution.

Sorting. Ordering the burst times ascending is the whole scheduling decision.

Prefix sums. Each job's waiting time is the running total of the burst times before it.

Exchange argument. Swapping a longer job earlier only increases total waiting — the proof that shortest-first wins.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The model

“Is scheduling preemptive?”

No — once a job starts it runs to completion, so order is decided up front.

“Do all jobs arrive at time 0?”

Yes — this is the classic SJF where only burst times matter.

The output

“Average of what, exactly?”

The waiting times — each job's delay before it starts — averaged and floored.

The ideal opening — say it like this

Average waiting time is minimized by running the shortest jobs first.

After sorting ascending, each job's wait is the sum of all burst times before it — a prefix sum.

I keep a running total of those prefix sums and divide by n at the end.

Understand the problem

Worked example — bt = [4, 3, 7, 1, 2]

sorted: 1 2 3 4 7
waits:  0 1 3 6 10        (each = running sum of earlier bursts)
total waiting = 20
average = 20 / 5 = 4

Key observations

1Aha

Shortest first minimizes total waiting

A job of length L delays every job scheduled after it by L. Placing short jobs first means fewer jobs are delayed by the long ones — provably the minimum total (and average) waiting time.

2Aha

Waiting times are prefix sums

After sorting, job i's waiting time is bt[0] + ... + bt[i-1]. So the total waiting time is the sum of all prefix sums — computable in one pass with a running accumulator.

3Aha

One running sum avoids the nested loop

Keep wait (the next job's waiting time) and add it to total before extending it by the current burst. That turns an O(n^2) double sum into a single O(n) sweep.

Brute force vs optimal

	Sum each prefix	Running prefix
Idea	For each job, re-add all earlier burst times	Carry a running waiting time as you sweep
Time	O(n^2) after sort	O(n log n) (the sort)
Space	O(1)	O(1)

Both sort first; the optimal just avoids recomputing each prefix from scratch. Full code is in the Approaches selector below.

Summary

Key takeaway

Sort burst times ascending (shortest job first), then each job's waiting time is the prefix sum of the bursts before it. Accumulate those with one running total and divide by n. Shortest-first is optimal because a long job early delays everyone behind it.

sort bt ascending
total = 0; wait = 0
for x in bt:
    total += wait      # this job waits for all earlier ones
    wait += x          # future jobs also wait for this one
return floor(total / n)