LeetCode 1701. Average Waiting Time Java Solution

Problem Description

• Problem: https://leetcode.com/problems/average-waiting-time/

• Description: The task is to calculate the average waiting time for all customers, considering each customer's arrival time and cooking time. Each customer can start their meal only after the previous customer's meal is finished.

Approach

• Idea:

  • Cooking time is always added to the current time. Whether a customer arrives early or late, it consumes the same amount of time.

  • If the current time is less than the customer's arrival time, update the current time to the customer's arrival time.

  • Given the arrival and cooking times of customers, calculate the time it takes from when the customer arrives until the meal is finished and add this to the total waiting time.

• Algorithm:

  1. Initialize totalWaitTime and currentTime variables.

  2. For each customer:

     • If the current time is less than the customer's arrival time, update the current time to the customer's arrival time.

     • Add the cooking time to the current time to calculate when the meal will be finished.

     • Add the time from the customer's arrival to the meal's finish to the total waiting time.

     • Update the current time to the meal's finish time.

  3. Divide the total waiting time by the number of customers to get the average waiting time.

Code

class Solution {
    public double averageWaitingTime(int[][] customers) {
        int n = customers.length;
        long totalWaitTime = 0;
        long currentTime = 0;

        for (int[] customer : customers) {
            int arrivalTime = customer[0];
            int cookingTime = customer[1];

            if (currentTime < arrivalTime) {
                currentTime = arrivalTime;
            }

            currentTime += cookingTime;
            totalWaitTime += (currentTime - arrivalTime);
        }

        return (double) totalWaitTime / n;
    }
}

Conclusion

• Time Complexity:

  • This algorithm has a time complexity of O(n) because it iterates through each customer once.

• Space Complexity:

  • The space complexity is O(1) since it uses a minimal amount of additional space.