{"id":974,"date":"2025-08-22T11:32:43","date_gmt":"2025-08-22T06:02:43","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=974"},"modified":"2025-08-22T11:32:44","modified_gmt":"2025-08-22T06:02:44","slug":"shortest-job-first","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/shortest-job-first\/","title":{"rendered":"Shortest Job first (SJF) | Greedy Algorithm"},"content":{"rendered":"\n

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

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Example 1<\/strong><\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>: bt = [3, 1, 2]<\/span><\/span>\nSJF<\/span> <\/span>order<\/span>: [1, 2, 3]<\/span><\/span>\nWaiting<\/span> <\/span>times<\/span>: [0, 1, 3]<\/span><\/span>\nAverage waiting time = (0 + 1 + 3) \/ 3 = 1.333..., answer = 1<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>: bt = [5, 5, 5]<\/span><\/span>\nSJF<\/span> <\/span>order<\/span>: [5, 5, 5]<\/span><\/span>\nWaiting<\/span> <\/span>times<\/span>: [0, 5, 10]<\/span><\/span>\nAverage waiting time = (0 + 5 + 10) \/ 3 = 5, answer = 5<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
The challenge is to pick an execution order that results in the smallest possible average waiting time and return its floor.<\/p>\n\n\n\n
\n\n\n\n
Intuition and Approach (Optimal Greedy)<\/h2>\n\n\n\n
For SJF with all arrivals at time 0, the optimal strategy is simple: sort the burst times in non-decreasing order<\/strong> and execute in that order. The reason is:<\/p>\n\n\n\n