问解决一系列问题所需的最少天数

EN

算法很简单。首先，按v_i对问题进行排序，然后，对于每个问题，查找(v_i-K, v_i]间隔中的问题数。这些数字中的最大值就是结果。第二阶段可以在O(n)中完成，因此最昂贵的操作是排序，从而使整个算法成为O(n log n)。Look here for a demonstration of the work of the algorithm on your data and K=35 in a spreadsheet.

为什么这是可行的

让我们将这个问题重新表述为图着色问题。我们创建图G如下:顶点将是问题，在两个问题之间将有一条边当且仅当|v_i - v_j| < K。

在这样的图中，独立集恰好对应于当天可做的问题集。(<=)如果集合可以在一天内完成，那么它肯定是一个独立的集合。(=>)如果集合中不包含两个不满足K-difference标准的问题，则只需按难易程度排序并按此顺序解决它们。这两个条件都将通过这种方式得到满足。

因此，很容易得出图G的颜色完全对应于问题在不同日期的时间表，每种颜色对应于一天。

因此，我们想要找出图G的色度，一旦我们认识到这个图是一个区间图，这是一个完美的图，那些色度等于团的图，这两个都可以通过一个简单的算法找到。

区间图是实线上的区间图，边是相交的区间之间的边。我们的图，很容易看到，是一个区间图(对于每个问题，分配一个区间(v_i-K, v_i]。很容易看出，这个区间图的边就是我们图的边)。

引理1:在区间图中，存在一个顶点，它的邻居形成一个团。

证明很简单。您只需取所有区间中具有最低上界(或最高下界)的区间。任何与其相交的区间都有较高的上界，因此，第一个区间的上界包含在它们的交集中。因此，他们彼此相交，形成了一个集团。qed

引理2:在导出子图上封闭的图族中，具有引理1(顶点的存在，其邻居形成团)的性质，以下算法产生最小着色：

从图中找出顶点x，它的邻域从图中形成一个clique.

• Remove x，使其子图G‘。

• G’

x by 上找不到的最少的颜色

证明:在(3)中，算法通过归纳假设+我们的族在诱导子图上的贴近度产生子图G‘的最优着色。在(4)中，该算法仅当在x的邻域上存在大小为n-1的团时才选择一个新的颜色n，也就是说，对于x，G中有一个大小为n的团，因此它的色度必须至少为n。因此，算法提供给顶点的颜色始终是<= chromaticity(G)，这意味着着色是最佳的。(显然，该算法会生成有效的着色)。qed

推论:区间图是完美的(完美<=>色度==团)

所以我们只需要找到G的团度，这对于区间图来说很容易:你只需处理不包含区间边界的实线的线段，并计算那里相交的区间数，这在你的例子中就更容易了，因为区间的长度是一致的。这导致了本文开头概述的算法。

我们真的需要转到路径覆盖吗？我们就不能遵循和LIS类似的策略吗？

输入按照复杂度递增的顺序排列。我们只需要为每天要执行的任务维护一堆队列。通过比较所有队列的最后一个元素，输入中的每个元素都将被分配到一天。只要我们发现'k‘的不同之处，我们就将任务附加到该列表中。

例如:5 3 4 5 6

1)输入-> 5(空列表，开始新列表)

5

2) 3(仅列表5& abs(5-3)是2 (k)，因此附加3)

5--> 3

3) 4(只列出最后的vi，3和abs(3-4) < k，所以开始一个新的列表)

5--> 3

4.

4) 5 (abs(3-5)=k追加)

5-->3-->5

4.

5) 6 (abs(5-6)

5-->3-->5

4-->6

我们只需要维护一个包含每个列表的最后一个元素的数组。由于天的顺序(当任务要完成时并不重要)，我们可以维护最后任务的排序列表，因此，搜索插入新任务的位置只是寻找值abs(vi-k)，这可以通过二进制搜索来完成。

复杂性：

该循环针对N个元素运行。在最坏的情况下，我们可能会使用二进制搜索(log i)来查询许多输入的ceil值。

因此，T( N ) < O( log！)= O(N log )。分析以确保上界和下界也是O( N log N )。复杂度为THETA (N log N)。

所需的最小天数将与G (DAG)的互补(无向)图中最长路径的长度相同。这可以用迪尔沃思定理来解决。