泡咖啡问题
泡咖啡问题
作者: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);
}
}
更多
相关文章
- [PHP] 解决宝塔面板运行php项目 pcntl_fork() has been disabled for security reasons
- 论文解读丨无参数的注意力模块SimAm
- 华为云企业级Redis揭秘第15期:Redis为什么需要强一致?
- 带你了解AKG正反向算子注册+关联流程
- 软件开发除了23种设计模式,还有7个开发原则需要了解
- Sechunter移动应用隐私合规检测详解
- 数仓如何限制临时数据文件下盘量
- 关于HTTPS认证,这里解决你所有疑惑
- 分析师机构发布中国低代码平台现状分析报告,华为云AppCube为数字化转型加码
- 云小课 | SA基线检查—给云服务的一次全面“体检”
- 并发高?可能是编译优化引发有序性问题
- 不止承上启下,带你了解工业物联网关
- 面试只要问到分布式,必问分布式锁
- 你真的懂Redis的5种基本数据结构吗?
- 从原理带你掌握Spring MVC拦截处理器知识
- 论文解读二十七:文本行识别模型的再思考
- 论文解读丨LayoutLM: 面向文档理解的文本与版面预训练
- 教你用SQL进行数据分析
- 解密并发幕后黑手:线程切换引发的原子性问题
- 云网络的守护神:主动链路监控