java - 基于时间的资源可用性

Question

我目前正在为处理事件调度的系统开发一个模块。每个事件对象都有一个开始和结束时间戳以及一组所需资源。每个资源的可用数量有限，同时发生的事件数量也有限制。最终，它类似于会议室预订类型系统，其中有有限数量的房间、投影仪、椅子等。

目前，我正在遍历当前事件以计算资源利用率和并发事件计数，但是当这涉及到数千个事件时，这似乎是一种低效的方法。

任何人都可以提出更有效的方法吗？

Answer 1

这就是所谓的NP 完全问题。随着样本量的增加，找到一个……说“数学上最优”的解决方案可能会变得非常昂贵。您花在...说“现实世界”解决方案上的时间取决于您的要求。通过使用一些启发式方法可以找到不太理想的解决方案。

一种启发式：

您可以按某些指标对模块进行排序。然后将它们按降序添加到您的池中。从最昂贵的模块开始。添加也适合同一插槽的所有模块。之后为其余模块打开一个新插槽。等等。