Shortest Job First

Intuition

The Shortest Job First (SJF) algorithm will be used to solve this problem. First, the job durations are sorted from shortest to longest to ensure the shortest job is handled next. After sorting, each job is processed in sequence, and the waiting time for each job is calculated by summing the durations of all previous jobs. This accumulated waiting time is then used to determine the total waiting time for all jobs.

Approach

Begin by sorting the job durations in ascending order so that the jobs are arranged from shortest to longest.
Initialize counters to keep track of the waiting time for each job and the total waiting time for all jobs.
Iterate through the sorted list of jobs. For each job, calculate its waiting time by summing the durations of all the previous jobs. Add the duration of the current job to the cumulative total time.
Once all jobs have been processed, calculate the average waiting time by dividing the total waiting time by the number of jobs.

Dry Run

Implementation of Shortest Job First Algorithm

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /*Function to calculate total waiting 
    time using Shortest Job First algorithm*/
    long long solve(vector<int>& bt) {
        // Sort jobs in ascending order
        sort(bt.begin(), bt.end());

        // Initialize total waiting time
        long long waitTime = 0;
        // Initialize total time taken
        long long totalTime = 0;
        // Get number of jobs
        int n = bt.size();

        // Iterate to calculate waiting time
        for (int i = 0; i < n; ++i) {
            waitTime += totalTime;
            totalTime += bt[i];
        }

        // Return average waiting time
        return waitTime/n;
    }
};

int main() {
    vector<int> jobs = {1, 2, 3, 4};

    cout << "Array Representing Job Durations: ";
    for (int i = 0; i < jobs.size(); i++) {
        cout << jobs[i] << " ";
    }
    cout << endl;

    Solution solution;
    long long ans = solution.solve(jobs);
    cout << "Total waiting time: " << ans << endl;

    return 0;
}
import java.util.*;

class Solution {
    /* Function to calculate total waiting 
       time using Shortest Job First algorithm */
    public long solve(int[] bt) {
        // Sort jobs in ascending order
        Arrays.sort(bt);

        // Initialize total waiting time
        long waitTime = 0;
        // Initialize total time taken
        long totalTime = 0;
        // Get number of jobs
        int n = bt.length;

        // Iterate to calculate waiting time
        for (int i = 0; i < n; ++i) {
            waitTime += totalTime;
            totalTime += bt[i];
        }

        // Return average waiting time
        return waitTime / n;
    }

    public static void main(String[] args) {
        int[] jobs = {1, 2, 3, 4};

        System.out.print("Array Representing Job Durations: ");
        for (int job : jobs) {
            System.out.print(job + " ");
        }
        System.out.println();

        Solution solution = new Solution();
        long ans = solution.solve(jobs);
        System.out.println("Total waiting time: " + ans);
    }
}
class Solution:
    """Function to calculate total waiting 
    time using Shortest Job First algorithm"""
    def solve(self, bt):
        # Sort jobs in ascending order
        bt.sort()

        # Initialize total waiting time
        wait_time = 0
        # Initialize total time taken
        total_time = 0
        # Get number of jobs
        n = len(bt)

        # Iterate to calculate waiting time
        for i in range(n):
            wait_time += total_time
            total_time += bt[i]

        # Return average waiting time
        return wait_time // n

# Example usage
if __name__ == "__main__":
    jobs = [1, 2, 3, 4]

    print("Array Representing Job Durations: ", end="")
    for job in jobs:
        print(job, end=" ")
    print()

    solution = Solution()
    ans = solution.solve(jobs)
    print("Total waiting time: ", ans)
class Solution {
    /* Function to calculate total waiting 
       time using Shortest Job First algorithm */
    solve(bt) {
        // Sort jobs in ascending order
        bt.sort((a, b) => a - b);

        // Initialize total waiting time
        let waitTime = 0;
        // Initialize total time taken
        let totalTime = 0;
        // Get number of jobs
        let n = bt.length;

        // Iterate to calculate waiting time
        for (let i = 0; i < n; ++i) {
            waitTime += totalTime;
            totalTime += bt[i];
        }

        // Return average waiting time
      return Math.floor(waitTime / n);
    }
}

// Example usage
const jobs = [1, 2, 3, 4];

console.log("Array Representing Job Durations: " + jobs.join(" "));

const solution = new Solution();
const ans = solution.solve(jobs);
console.log("Total waiting time: " + ans);

Complexity Analysis

Time Complexity: O(N logN + N) where N is the length of the jobs array.The code first sorts the job durations, which takes O(N logN) time. After sorting, it iterates through the job durations to calculate the total waiting time, which takes O(N) time. Space Complexity: O(1) no extra space used.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code