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:
Initialize
totalWaitTime
andcurrentTime
variables.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.
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.
Subscribe to my newsletter
Read articles from Han directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by