泡咖啡問題
泡咖啡問題
作者：Grey
原文地址：
題目描述
數組 arr 中記錄每個咖啡機製造一杯咖啡的時間，假設有 m 個人，都在 0 號時間點開始排隊，返回一個長度為 m 的數組，代表每個人得到咖啡的時間，
要求：最後一個得到咖啡的人的時間儘可能短。
主要思路
定義咖啡機這個數據結構
public static class CoffeeMachine {
public int start;
public int work;
public CoffeeMachine(int s, int w) {
start = s;
work = w;
}
@Override
public String toString() {
return "CoffeeMachine{" + "start=" + start + ", work=" + work + '}';
}
}
其中
start 變量表示這個咖啡機什麼時候可以空閑，
work 變量表示這個咖啡機製作一杯咖啡的時間，
接下來，設置一個小根堆（Java 中就是 PriorityQueue），小根堆存放的就是咖啡機的信息，小根堆的比較策略就是：咖啡機開始工作的時間加上這個咖啡機製作一杯咖啡的時間之和越小的在堆頂。
每次做完一杯咖啡以後，彈出，記錄下此時的時間存入結果數組，並且修改此時的咖啡機的開始工作時間，再次壓入小根堆，然後小根堆彈出下一個元素，如此往複，一直到小根堆彈出 m 個元素。
例如
首先把所有咖啡機放入小根堆，第一個彈出的咖啡機是 CoffeeMachine{start=0, work=2}
0 號小人使用 CoffeeMachine{start=0, work=2} 咖啡機
此時這個咖啡機的參數變為 CoffeeMachine{start=2, work=2}
把改變後的咖啡機放入小根堆，再次彈出一個咖啡機，此時
CoffeeMachine{start=0, work=3} 咖啡機被彈出
1 號人使用 CoffeeMachine{start=0, work=3} 咖啡機
此時這個咖啡機的參數變為 CoffeeMachine{start=3, work=3}
把改變後的咖啡機放入小根堆，再次彈出一個咖啡機，此時
CoffeeMachine{start=2, work=2} 咖啡機被彈出
2 號人使用 CoffeeMachine{start=2, work=2} 咖啡機
此時這個咖啡機的參數變為 CoffeeMachine{start=4, work=2}
把改變後的咖啡機放入小根堆，再次彈出一個咖啡機，此時
CoffeeMachine{start=0, work=5} 咖啡機被彈出
3 號人使用 CoffeeMachine{start=0, work=5} 咖啡機
此時這個咖啡機的參數變為 CoffeeMachine{start=5, work=5}
把改變後的咖啡機放入小根堆，再次彈出一個咖啡機，此時
CoffeeMachine{start=4, work=2} 咖啡機被彈出
4 號人使用 CoffeeMachine{start=4, work=2} 咖啡機
此時這個咖啡機的參數變為 CoffeeMachine{start=6, work=2}
完整代碼如下
import java.util.PriorityQueue;
public class Code_Coffee {
public static class CoffeeMachine {
@Override
public String toString() {
return "CoffeeMachine{" + "start=" + start + ", work=" + work + '}';
}
public int start;
public int work;
public CoffeeMachine(int s, int w) {
start = s;
work = w;
}
}
public static int[] bestChoices(int[] arr, int m) {
int[] ans = new int[m];
PriorityQueue<CoffeeMachine> heap = new PriorityQueue<>((o1, o2) -> o1.start + o1.work - o2.start - o2.work);
for (int coffeeWork : arr) {
// 製造咖啡最短時間的咖啡機在堆頂
heap.add(new CoffeeMachine(0, coffeeWork));
}
for (int i = 0; i < m; i++) {
CoffeeMachine cur = heap.poll();
// 第i號人使用cur這個咖啡機，所以cur這個咖啡機的開始時間變為cur.start + cur.work
System.out.println(i + " 號人使用 " + cur + "咖啡機");
ans[i] = cur.start + cur.work;
System.out.println(i + " 號人在 [" + cur.start + "] 時刻搞定完一杯咖啡");
cur.start = ans[i];
heap.add(cur);
}
return ans;
}
public static void main(String[] args) {
int m = 5;
int[] arr = {2, 3, 5};
bestChoices(arr, m);
}
}
