There is a queue for the self-checkout tills at the supermarket. Your task is write a function to calculate the total time required for all the customers to check out!
The function has two input variables:
- customers: an array (list in python) of positive integers representing the queue. Each integer represents a customer, and its value is the amount of time they require to check out.
- n: a positive integer, the number of checkout tills.
The function should return an integer, the total time required.
EDIT:A lot of people have been confused in the comments. To try to prevent any more confusion:
- There is only ONE queue, and
- The order of the queue NEVER changes, and
- Assume that the front person in the queue (i.e. the first element in the array/list) proceeds to a till as soon as it becomes free.
- The diagram on the wiki page I linked to at the bottom of the description may be useful.
Good Solution1:
import java.util.Arrays;
public class Solution {
public static int solveSuperMarketQueue(int[] customers, int n) {
int[] result = new int[n];
for(int i = 0; i < customers.length; i++){
result[0] += customers[i];
Arrays.sort(result);
}
return result[n-1];
}
}
Good Solution2:
import java.util.*;
public class Solution {
public static int solveSuperMarketQueue(int[] customers, int n) {
if (customers.length == 0)
return 0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < customers.length && i < n; i++)
pq.offer(customers[i]);
for (int i = n; i < customers.length; i++)
pq.offer(pq.poll() + customers[i]);
while (pq.size() != 1)
pq.poll();
return pq.poll();
}
}
