Shortest Job First

All jobs are available at time 0. The positive integer array bt contains their burst durations. Run one job at a time without preemption, using…

All jobs are available at time 0. The positive integer array `bt` contains their burst durations. Run one job at a time without preemption, using shortest-job-first order. A job waits for the sum of durations of all earlier jobs. Return the floor of the average waiting time over all jobs. Return an average, not total waiting time or total elapsed time.

- 1 <= bt.length <= 100000 - 1 <= bt[i] <= 100000 - All jobs are available before scheduling; no arrival times are supplied. - Use wide arithmetic: the result may be 4999950000 and total waiting time may be 499995000000000. - The teaching trace accepts at most 8 jobs; coding retains the full bounds.

Example 1: input bt = [4,1,3,7,2]; output 4. Sorted order [1,2,3,4,7] has waiting times [0,1,3,6,10], totaling 20.

Example 2: input bt = [1,2,3,4]; output 2. The waiting total is 10; floor(10/4) is 2.

Example 3: input bt = [1,2]; output 0. Waiting times are [0,1], so floor(1/2) is 0.

Category: Greedy Algorithms. Topic: greedy. Difficulty: Medium. Patterns: greedy, sorting.