题目
酒馆里酒馆里有m个龙头可供顾客们接啤酒，每个龙头每秒的出酒量相等，都是1。现有n名顾客准备接酒，他们初始的接酒顺序已经确定。将这些顾客按接酒顺序从1到n编号，i号顾客的接酒量为w[i]。接酒开始时，1到m号顾客各占一个酒龙头，并同时打开龙头接酒。当其中某个顾客j完成其接酒量要求w[j]后，下一名排队等候接酒的顾客k马上接替j顾客的位置开始接酒。这个换人的过程是瞬间完成的，且没有任何酒的浪费。即j顾客第x秒结束时完成接酒，则k顾客第x+1秒立刻开始接酒。若当前接酒人数n不足m，则只有n个龙头供酒，其它m-n个龙头关闭。 现在给出n名顾客的接酒量，按照上述规则，问所有顾客都接完酒需要多少秒？
题目分析
对于这道题目，因为有n个顾客接酒，因此我们至少需遍历整个输入数组一次，则算法的时间复杂度不可能低于O(n)。考虑到总计有m个水龙头，因此同时可以有m个人接酒。而结束最早的总当前正在接酒的用户中所需酒量最少的人。也就是说我们每次都需要找到结束时间最早的人。那么使用最小堆就能够非常方便地实现这一目的。使用最小堆保存当前正在接酒的用户的结束时间，我们就可以在O(1)时间内决定当前m个正在接酒的人中哪一个最先结束。同时最小堆重新heapify的时间为O(logm)。我们只要重复这一过程，在最小堆的大小小于m的时候不断向其中添加用户的结束时间，然后取出结束时间最早的用户，得到其结束时间作为当前时间，并在当前时间的基础上加上排队的用户中下一个需要接酒的时间并放入堆中，则最后一个从堆中被取出的时间为所有用户接酒所需的时间。
时空复杂度
使用了一个大小为m的最小堆保存正在接酒的用户。因此空间复杂度为O(m)。
遍历了一遍所有用户，此为O(n)，同时每个用户都被放入堆中及从堆中取出一次，取出为O(1)，取出后堆重新heapify为O(logm)，放入为O(logm)，因此时间复杂度为O(nlogm)。
算法实现如下
public class GetBeerForAll {
public static int getBeer(int[] clients, int beerTap) {
// Deal with invalid inputs
if (clients == null || clients.length == 0 || beerTap == 0) {
return -1;
}
PriorityQueue<Integer> currClients = new PriorityQueue<>();
int index = 0; // the index of the next clients that will use the beer tap
int currTime = 0; // current time.
while (index < clients.length || !currClients.isEmpty()) {
// As long as the number of clients that is using beer tap right now is less
// than the total number of beer tap and there is more clients in line,
// we can put more clients into the PriorityQueue
// that contains the clients currently served by beer tap.
while(currClients.size() < beerTap && index < clients.length) {
currClients.add(clients[index++] + currTime);
}
// Otherwise, all clients is either already been served or is currently being served,
// constantly poll out the clients that finished the earliest and renew the current time
// until all clients finished.
// At this time, current time is the time that all clients have been served.
currTime = currClients.poll();
}
return currTime;
}
}
