Shortest Job First
Problem link: https://www.geeksforgeeks.org/problems/shortest-job-first/1
Problem Statement
Given an array of integers burstTime[] representing the burst time of processes, find the average waiting time using the Shortest Job First (SJF) scheduling algorithm.
In SJF, processes are executed in increasing order of their burst time.
Input
An array burstTime[] of size n representing execution time of each process.
Output
Return the average waiting time of all processes.
Example
Input: burstTime = [6, 8, 7, 3]
Output: 7
Explanation
Step 1: Sort burst times → [3,6,7,8] Step 2: Waiting times: First process = 0 Second = 3 Third = 3 + 6 = 9 Fourth = 3 + 6 + 7 = 16
Total waiting time = 0 + 3 + 9 + 16 = 28 Average = 28 / 4 = 7
Brute Force
Intuition
Try all possible execution orders and compute waiting time. This guarantees the minimum but is computationally infeasible.
Approach
- Generate all permutations of burstTime
- For each permutation:
- Calculate total waiting time
- Return minimum average waiting time
Dry Run
Compare different orders like [6,8,7,3] vs [3,6,7,8]. Sorted order gives minimum waiting time.
Code (Java)
public class Solution {
public int solve(int[] bt) {
Arrays.sort(bt);
int wait = 0, total = 0;
for (int i = 0; i < bt.length; i++) {
total += wait;
wait += bt[i];
}
return total / bt.length;
}
}
Complexity Analysis
Generating all permutations leads to factorial time complexity, which is impractical.
Optimal Solution
Intuition
Executing shorter jobs first minimizes cumulative waiting time because longer jobs delay more processes if placed earlier.
Approach
- Sort burstTime array in ascending order
- Initialize wait = 0, total = 0
- For each process:
- Add current wait to total
- Increase wait by burstTime[i]
- Return total / n
Dry Run
Sorted = [3,6,7,8] Wait = 0 → 3 → 9 → 16 Total = 28 Average = 7
Code (Java)
import java.util.*;
public class Solution {
public int solve(int[] bt) {
Arrays.sort(bt);
int wait = 0, total = 0;
for (int i = 0; i < bt.length; i++) {
total += wait;
wait += bt[i];
}
return total / bt.length;
}
}
Complexity Analysis
Sorting dominates the time complexity. No extra space is required apart from variables.
Quick Revision (Brute Force)
- Try all permutations
- Compute waiting time
- Pick minimum
Quick Revision (Optimal)
- Sort burst times
- Accumulate waiting time
- Return average