Problem Statement

You are given an array of n integers where each integer represents the burst time of a process (the time the process takes to complete). Using the Shortest Job First (SJF) or Shortest Job Next (SJN) scheduling policy, determine the average waiting time for all processes. The waiting time for a process is the total time it waits before its execution starts. You need to return the closest whole number that is less than or equal to the average waiting time.

Examples

Example 1:

Input: burst_times = [4, 1, 3, 7, 2]
Output: 4

Explanation: 

Different Approaches

1️⃣ Greedy Approach

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:

1. Begin by sorting the job durations in ascending order so that the jobs are arranged from shortest to longest.
2. Initialize counters to keep track of the waiting time for each job and the total waiting time for all jobs.
3. 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.
4. Once all jobs have been processed, calculate the average waiting time by dividing the total waiting time by the number of jobs.

Dry Run:

Initialization:

totalWaitingTime = 0
currentWaitingTime = 0
       +-----+-----+-----+-----+-----+
jobs = |  4  |  3  |  7  |  1  |  2  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4

Sort the Jobs in Ascending Order:

totalWaitingTime = 0
currentWaitingTime = 0
       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5

First Iteration:

totalWaitingTime = 0
currentWaitingTime = 0

       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5
          ^
          |
          i
   totalWaitingTime += currentWaitingTime
   totalWaitingTime = 0 + 0
                    = 0
   currentWaitingTime += jobs[i]
   currentWaitingTime = 0 + 1
                      = 1

Second Iteration:

totalWaitingTime = 0
currentWaitingTime = 1

       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5
                ^
                |
                i
   totalWaitingTime += currentWaitingTime
   totalWaitingTime = 0 + 0
                    = 0
   currentWaitingTime += jobs[i]
   currentWaitingTime = 1 + 2
                      = 3

Third Iteration:

totalWaitingTime = 1
currentWaitingTime = 3

       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5
                      ^
                      |
                      i
   totalWaitingTime += currentWaitingTime
   totalWaitingTime = 1 + 3
                    = 4
   currentWaitingTime += jobs[i]
   currentWaitingTime = 3 + 3
                      = 6

Fourth Iteration:

totalWaitingTime = 4
currentWaitingTime = 6

       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5
                            ^
                            |
                            i
   totalWaitingTime += currentWaitingTime
   totalWaitingTime = 4 + 6
                    = 10
   currentWaitingTime += jobs[i]
   currentWaitingTime = 6 + 4
                      = 10

Fifth Iteration:

totalWaitingTime = 10
currentWaitingTime = 10

       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5
                                  ^
                                  |
                                  i
   totalWaitingTime += currentWaitingTime
   totalWaitingTime = 10 + 10
                    = 20
   currentWaitingTime += jobs[i]
   currentWaitingTime = 10 + 7
                      = 17

Loop Termination:

totalWaitingTime = 20
currentWaitingTime = 17

       +-----+-----+-----+-----+-----+
jobs = |  1  |  2  |  3  |  4  |  7  |
       +-----+-----+-----+-----+-----+
 index    0     1     2     3     4
         P1    P2    P3    P4    P5
                                        ^
                                        |
                                        i
   Since i has crossed the bounds of the array,
   now totalWaitingTime variable contains the 
   complete waiting time of all the jobs.
   
   just divide the totalWaitingTime with the
   size of the jobs array to get the average
   waiting time.
   
   average waiting time  = totalWaitingTime / jobs.size()
   average waiting time = 20 / 5
                        = 4

Code:

#include <iostream>
#include <vector>
#include <algorithm> // For sort function
using namespace std;

// Function to calculate average waiting time using SJF scheduling
int calculateAverageWaitingTime(vector<int>& burstTimes) {
    int n = burstTimes.size();
    
    // Sort the burst times to implement the SJF policy
    sort(burstTimes.begin(), burstTimes.end());
    
    int totalWaitingTime = 0;  // Total waiting time for all processes
    int currentWaitingTime = 0; // Waiting time for the current process
    
    // Loop through the sorted burst times and calculate waiting times
    for (int i = 0; i < n; ++i) {
        totalWaitingTime += currentWaitingTime;
        currentWaitingTime += burstTimes[i];  // Update waiting time for the next process
    }
    
    // Calculate average waiting time and return the floor of the result
    return totalWaitingTime / n;  // Since we want floor, integer division suffices
}

int main() {
    // Example burst times
    vector<int> burstTimes = {5, 1, 8, 3};
    
    // Calculate and print the average waiting time
    int avgWaitingTime = calculateAverageWaitingTime(burstTimes);
    cout << "Average Waiting Time (floor): " << avgWaitingTime << endl;

    return 0;
}

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.