145. Shortest Job First (SJF) CPU Scheduling - Average Waiting Time

Given the burst times of n processes, all of which arrive at time 0, and scheduled non-preemptively by shortest burst time first, find the average waiting time across all processes. Print it with exactly two decimal places.

Input: The first line contains an integer n, the number of processes. The second line contains n space-separated integers, the burst time of each process (all arriving at time 0). Output: Print a single floating-point number - the average waiting time across all processes - formatted to exactly two decimal places.

1 <= n <= 10^5

SJF minimizes AVERAGE waiting time, but it's not necessarily 'fair' - a long job could theoretically wait a very long time if many short jobs keep arriving (a real practical concern called 'starvation', usually mentioned as a tradeoff when discussing SJF in OS contexts).

Schedule processes by shortest burst time first, and find the average time each process waits. Brute force: Try every possible ordering of processes and compute the average waiting time for each - this is factorial time, impractical, when SJF is a well-known, provably optimal ordering for minimizing average waiting time. Optimised: Running the SHORTEST jobs first is provably optimal for minimizing AVERAGE waiting time - an exchange argument shows that swapping any two out-of-order (by burst time) adjacent jobs to be in ascending order never increases the total waiting time, so full ascending sort achieves the minimum.

Sort the burst times in ascending order using an efficient comparison sort, then simulate the schedule in one linear pass: each process's waiting time is the sum of all burst times scheduled before it (waiting[i] = waiting[i-1] + burst[i-1]), and the average is the total waiting time divided by n. Sorting once replaces the repeated linear scans of the selection-based approach, so the same correct ordering is produced in log-linear rather than quadratic time. Time: O(n log n) Space: O(n)

Repeatedly scan the remaining unscheduled processes to find the one with the smallest burst time, append it next to the schedule, and remove it from consideration - effectively performing a selection sort of the burst times. This is correct because SJF's optimality only requires that processes run in non-decreasing order of burst time, and building that order via repeated linear-scan selection achieves it, just less efficiently than a dedicated sort. Time: O(n^2) Space: O(n)

Try every possible ordering (permutation) of the n processes, compute the resulting waiting times and their average for each ordering, and keep the minimum average found. This is guaranteed to find the true minimum since it considers every possible schedule, but the number of permutations grows factorially, making it usable only for tiny n. Time: O(n! * n) Space: O(n)

1. Sort the burst times in ascending order - this IS exactly the schedule SJF produces. 2. The waiting time of the process at sorted position i is the sum of ALL burst times before it (since they all run first). 3. Sum all these waiting times and divide by the number of processes for the average.

Time: O(n log n), dominated by sorting the burst times. Space: O(1) extra space beyond the sort and a running prefix sum.

n = 1 (waiting time is 0.00), n = 10^5 for performance, and processes sharing equal burst times where relative order among ties doesn't affect the average.

Be ready to explain the exchange argument for why SJF minimizes AVERAGE waiting time specifically - a classic proof technique worth having ready for CPU scheduling and similar 'ordering to minimize a sum' problems.