題目

酒館里酒館里有m個龍頭可供顧客們接啤酒，每個龍頭每秒的出酒量相等，都是1?，F(xiàn)有n名顧客準(zhǔn)備接酒，他們初始的接酒順序已經(jīng)確定。將這些顧客按接酒順序從1到n編號，i號顧客的接酒量為w[i]。接酒開始時，1到m號顧客各占一個酒龍頭，并同時打開龍頭接酒。當(dāng)其中某個顧客j完成其接酒量要求w[j]后，下一名排隊等候接酒的顧客k馬上接替j顧客的位置開始接酒。這個換人的過程是瞬間完成的，且沒有任何酒的浪費(fèi)。即j顧客第x秒結(jié)束時完成接酒，則k顧客第x+1秒立刻開始接酒。若當(dāng)前接酒人數(shù)n不足m，則只有n個龍頭供酒，其它m-n個龍頭關(guān)閉。 現(xiàn)在給出n名顧客的接酒量，按照上述規(guī)則，問所有顧客都接完酒需要多少秒？

題目分析

對于這道題目，因為有n個顧客接酒，因此我們至少需遍歷整個輸入數(shù)組一次，則算法的時間復(fù)雜度不可能低于O(n)?？紤]到總計有m個水龍頭，因此同時可以有m個人接酒。而結(jié)束最早的總當(dāng)前正在接酒的用戶中所需酒量最少的人。也就是說我們每次都需要找到結(jié)束時間最早的人。那么使用最小堆就能夠非常方便地實現(xiàn)這一目的。使用最小堆保存當(dāng)前正在接酒的用戶的結(jié)束時間，我們就可以在O(1)時間內(nèi)決定當(dāng)前m個正在接酒的人中哪一個最先結(jié)束。同時最小堆重新heapify的時間為O(logm)。我們只要重復(fù)這一過程，在最小堆的大小小于m的時候不斷向其中添加用戶的結(jié)束時間，然后取出結(jié)束時間最早的用戶，得到其結(jié)束時間作為當(dāng)前時間，并在當(dāng)前時間的基礎(chǔ)上加上排隊的用戶中下一個需要接酒的時間并放入堆中，則最后一個從堆中被取出的時間為所有用戶接酒所需的時間。

時空復(fù)雜度

使用了一個大小為m的最小堆保存正在接酒的用戶。因此空間復(fù)雜度為O(m)。

遍歷了一遍所有用戶，此為O(n)，同時每個用戶都被放入堆中及從堆中取出一次，取出為O(1)，取出后堆重新heapify為O(logm)，放入為O(logm)，因此時間復(fù)雜度為O(nlogm)。

算法實現(xiàn)如下

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;
    }
}