algorithm - 优化日历块算法

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 周三周二周六周日

等等

问题是要提出一个可行的算法（从性能、内存的角度来看，并且没有量化计算机 :)，它提出了最少的跨度来描述给定的时期（没有保证的最小数量但是，即使那会很好:)。跨度可能重叠。

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

Answer 1

该问题与使用卡诺图的电路最小化有一些相似之处。众所周知，这个问题是 NP 难的，因此像Quine-McCluskey 算法这样的算法这样的算法具有指数运行时间。

因此，我的意图告诉我，您的问题没有有效的算法。还有很多其他的覆盖问题，比如顶点覆盖和集合覆盖，它们也是非常困难的问题。我会尝试证明设置封面可以减少到您的问题，使您的问题也变得 NP-hard。