algorithm - 优化日历 block 算法

Question

所以这是一个棘手的问题，它有所简化但基于与内存优化有关的现实世界问题(它不是家庭作业)

假设您是两个日期之间的一段时间(例如 2013-01-01 到 2013-01-31)。现在你得到了一堆日期条目，每个条目都包含一个日期和一种颜色。每个日期最多有一个条目，但可能不是所有日期都有条目。

例如:

2013-01-01 黄色

2013-01-02 蓝色

2013-01-03 红色

2013-01-05 黄色

等等

现在假设我们有一个包含开始日期、结束日期和颜色的跨度。我们还有一个可选的星期几过滤器，如果声明，它可以包含一周中的一天或几天。在那些情况下，跨度仅在那些日子“活跃”。

例如在下面的例子中我们可能有:

跨度 #1:2013-01-01 - 2013-01-06 蓝色

跨度 #2:2013-01-13 - 2013-01-27 红色星期一

跨度 #3:2013-01-08 - 2013-01-26 CYAN Wed Tue Sat Sun

等等

问题是想出一个可行的算法(从性能、内存的角度来看，没有定量计算机 :)，它能用最少的跨度来描述给定的时期(没有保证最低金额，但即使这样也很好 :) 。跨度可能重叠。

暴力破解看起来很讨厌，但应该有一个优雅的解决方案

Answer 1

这个问题与circuit minimization有一些相似之处使用 Karnaugh maps .已知此问题是 NP-hard 问题，因此像 Quine–McCluskey algorithm 这样的算法具有指数运行时间。

因此，我的意图告诉我，对于您的问题，没有有效的算法。还有很多其他覆盖问题，例如 vertex cover和 set cover它们也是非常困难的问题。我会尝试证明集合覆盖可以简化为您的问题，使您的问题也成为 NP-hard。