Shortest Job first (SJF) | Greedy Algorithm

You are given a list of CPU burst times for processes that all arrive at time 0. Using Shortest Job First (SJF), non-preemptive, schedule the processes to minimize the average waiting time. You need to return the floor of the average waiting time as per the GFG requirement.

Here’s the [Problem Link] to begin with.

Example 1

Input: bt = [3, 1, 2]
SJF order: [1, 2, 3]
Waiting times: [0, 1, 3]
Average waiting time = (0 + 1 + 3) / 3 = 1.333..., answer = 1

Example 2

Input: bt = [5, 5, 5]
SJF order: [5, 5, 5]
Waiting times: [0, 5, 10]
Average waiting time = (0 + 5 + 10) / 3 = 5, answer = 5

The challenge is to pick an execution order that results in the smallest possible average waiting time and return its floor.

Intuition and Approach (Optimal Greedy)

For SJF with all arrivals at time 0, the optimal strategy is simple: sort the burst times in non-decreasing order and execute in that order. The reason is:

• A shorter job placed earlier keeps the cumulative waiting time of all following jobs smaller.
• This is a classic exchange argument. If a longer job is before a shorter job, swapping them never increases and usually decreases the total waiting time.

Once sorted:

• The waiting time of a process equals the sum of burst times of all previous processes.
• Maintain a running prefix sum of burst times to accumulate total waiting time.
• Compute floor(total_waiting_time / n) to match GFG output.

Code Implementation

Your provided optimal greedy solution with minimal comments only:

class Solution:
    def solve(self, bt):
        # Sort burst times (Greedy: always pick shortest job first)
        bt.sort()
        
        n = len(bt)
        waiting_time = 0
        total_waiting_time = 0
        
        # Calculate waiting times
        for i in range(1, n):
            waiting_time += bt[i-1]   # Add previous process burst time
            total_waiting_time += waiting_time
        
        # Average waiting time
        avg_waiting_time = total_waiting_time // n   # floor division as per GFG
        
        return avg_waiting_time

Code explanation

• Sort burst times so that shorter jobs execute first.
• Use a running prefix sum waiting_time that adds the previous job’s burst each step.
• Accumulate total_waiting_time by adding the current waiting_time for each process starting from index 1.
  The first job waits 0, the second waits bt[0], the third waits bt[0] + bt[1], and so on.
• Finally, compute the floor of the average using integer division //.

Time and Space Complexity

• Precise: sorting takes O(n log n), the single pass accumulation takes O(n), so total O(n log n + n)
• Simplified: O(n log n) time
• Space: sorting in place and constant extra variables give O(1) extra space

Conclusion

For Shortest Job First with all processes available at time 0, sorting the burst times and computing prefix sums yields the minimum average waiting time. The greedy approach is optimal, easy to implement, and runs in O(n log n) time with O(1) extra space.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.