Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from currentTime = 0 and increment it by preparation time of the current order (as only one order can be prepared at any given time). When that order is complete, look for customers whose order/arrival time is before or equal to the current time. It goes on till all the customers are served.
InputStreamReader inputStreamReader = new InputStreamReader(System.in);
Scanner scanner = new Scanner(fileReader);
int noOfCustomers = scanner.nextInt();
int[] arrivalTime = new int[noOfCustomers];
int[] orderPreparationTime = new int[noOfCustomers];
int i = 0;
while (scanner.hasNext()) {
arrivalTime[i] = scanner.nextInt();
orderPreparationTime[i] = scanner.nextInt();
i++;
}
int[] weightTimes = new int[noOfCustomers];
int customersServed = 0;
int currentTime = 0;
while (customersServed < noOfCustomers) {
int minWeightTime = Integer.MAX_VALUE;
int customerIndex = Integer.MIN_VALUE;
int preparationTime = 0;
for (int j = 0; j < noOfCustomers; j++) {
if (arrivalTime[j] <= currentTime) {
int weightTime = (currentTime - arrivalTime[j] + orderPreparationTime[j]);
if (weightTime < minWeightTime) {
minWeightTime = weightTime;
customerIndex = j;
preparationTime = orderPreparationTime[j];
}
}
}
if (customerIndex != Integer.MIN_VALUE) {
weightTimes[customerIndex] = minWeightTime;
arrivalTime[customerIndex] = Integer.MAX_VALUE;
customersServed++;
currentTime += preparationTime;
}
}
int totalWeightTime = 0;
for (int weightTime : weightTimes) {
totalWeightTime += weightTime;
}
System.out.println((int) totalWeightTime / noOfCustomers);
Input (Arrival Time, Order time) for 6 customers:
6
0 3
1 9
2 5
4 4
4 7
5 3
