泡咖啡问题

作者：Grey

原文地址：

博客园：泡咖啡问题

CSDN：泡咖啡问题

题目描述

数组 arr 中记录每个咖啡机制造一杯咖啡的时间，假设有 m 个人，都在 0 号时间点开始排队，返回一个长度为 m 的数组，代表每个人得到咖啡的时间，

要求：最后一个得到咖啡的人的时间尽可能短。

主要思路

设置一个小根堆，Java 中就是 PriorityQueue，小根堆的比较策略就是：咖啡机开始工作的时间加上这个咖啡机制作一杯咖啡的时间之和越小的在堆顶。

每次做完一杯咖啡以后，弹出，记录下此时的时间存入结果数组，并且修改此时的咖啡机的开始工作时间，再次压入小根堆，然后小根堆弹出下一个元素，如此往复，一直到小根堆弹出 m 个元素。

完整代码如下

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

如上示例，运行 main 方法，可以得到结果

0 号人使用 CoffeeMachine{start=0, work=2}咖啡机
0 号人在 [0] 时刻搞定完一杯咖啡
1 号人使用 CoffeeMachine{start=0, work=3}咖啡机
1 号人在 [0] 时刻搞定完一杯咖啡
2 号人使用 CoffeeMachine{start=2, work=2}咖啡机
2 号人在 [2] 时刻搞定完一杯咖啡
3 号人使用 CoffeeMachine{start=0, work=5}咖啡机
3 号人在 [0] 时刻搞定完一杯咖啡
4 号人使用 CoffeeMachine{start=4, work=2}咖啡机
4 号人在 [4] 时刻搞定完一杯咖啡

更多

算法和数据结构笔记