线性复杂度的调度算法

Question

以下是问题：

我们有n个任务需要在n天内完成。每天我们只能完成一个任务。每个任务都有一个开始日期和结束日期。我们不能在开始日期之前开始任务，也必须在结束日期之前完成任务。因此，给定一个开始日期向量s和一个结束日期向量e，如果存在向量d，其中d[i]是你完成任务i的日期。例如：

s = {1, 0, 1, 2, 0}
e = {2, 4, 2, 3, 1}

+--------+------------+----------+
| Task # | Start Date | End Date |
+--------+------------+----------+
|      0 |          1 |        2 |
|      1 |          0 |        4 |
|      2 |          1 |        2 |
|      3 |          2 |        3 |
|      4 |          0 |        1 |
+--------+------------+----------+

我们有一个可能的解决方案：

d = {1, 4, 2, 3, 0}

+--------+----------------+
| Task # | Date Completed |
+--------+----------------+
|      0 |              1 |
|      1 |              4 |
|      2 |              2 |
|      3 |              3 |
|      4 |              0 |
+--------+----------------+

创建一个O(n^2)时间复杂度的算法很容易。创建一个O(nlogn)时间复杂度的算法也不算太糟糕。据说有一种算法可以在O(n)时间内得出解决方案。那是什么算法呢？

- Maxime Michel

---

这个问题的根源是什么？ - Douglas Zare

我已经尝试过解决这个问题，但是没有成功。在我投入更多的时间之前，我想确保该问题确实已知具有O(n)的解决方案。你是否有任何来源声称存在O(n)的解决方案？预处理数据是否被允许？最坏情况下或平均情况下应该是O(n)吗？ - Asad Saeeduddin

如果一个人已经知道旅行商问题是NP难的（正如它所是的那样），那么具有序列依赖设置的作业车间问题显然也是NP难的，因为TSP是JSP的特例，其中m = 1（推销员是机器，城市是工作），因此调度算法是NP难的！ - eliasah

我非常确定这个问题的时间复杂度不可能比O(nlogn)更快。以所有工作都在第一天开始，它们的结束日期都是唯一的且小于n为例，因此对于n=5，您有s=[0,0,0,0,0]和e=[0,3,1,4,2]。显然，唯一的调度方式是完成最快结束的任务。但我能想到的唯一方法是对它们进行排序，这是O(nlogn)的。您在哪里读到这个问题可以在O(n)内解决？输入向量是否已经排序？ - woojoo666

Answer 1

当你不能使用时间时，可以使用空间！您可以使用位向量表示任何一天打开的任务。在O(n)中创建一个“从今天开始”的数组。您还可以使用另一个位向量表示最快结束的任务，这也可以在O(n)中计算。最后，在O(n)中扫描每天，添加在该天开始的任何任务，选择该天开放的编号最低的任务，优先考虑最快结束的任务。

using System.IO;
using System;
using System.Math;

class Program
{
    static void Main()
    {
        int n = 5;

        var s = new int[]{1, 0, 1, 2, 0};
        var e = new int[]{2, 4, 2, 3, 1};

        var sd = new int[n];
        var ed = new int[n];
        for (int task = 0; task < n; task++)
        {
            sd[s[task]] += (1 << task);  // Start for task i
            ed[e[task]] += (1 << task);  // End for task i
        }

        int bits = 0;

        // Track the earliest ending task
        var ends = new int[n];
        for (int day = n-1; day >= 0; day--)
        {
            if (ed[day] != 0)           // task(s) ending today
            {
                // replace any tasks that have later end dates
                bits = ed[day];
            }
            ends[day] = bits;
            bits = bits ^ sd[day];       // remove any starting
        }

        var d = new int[n];
        bits = 0;
        for (int day = 0; day < n; day++)
        {
            bits |= sd[day];              // add any starting

            int lowestBit;

            if ((ends[day] != 0) && ((bits & ends[day]) != 0))
            {
                // Have early ending tasks to deal with
                // and have not dealt with it yet
                int tb = bits & ends[day];
                lowestBit = tb & (-tb);
                if (lowestBit == 0) throw new Exception("Fail");
            }
            else
            {
                lowestBit = bits & (-bits);
            }
            int task = (int)Math.Log(lowestBit, 2);

            d[task] = day;
            bits = bits - lowestBit;      // remove task
        }

        Console.WriteLine(string.Join(", ", d));
    }
}

在这种情况下的结果是：1、4、2、3、0，正如预期的那样。

- Ian Mercer

---

输出数组代表什么？它似乎与预期输出不匹配。 - Asad Saeeduddin

好的，这是转置。很容易修复。已修复。 - Ian Mercer

就此而言，这与我尝试解决的问题相同。我使用集合编写了一个贪心算法，它给出了{1,0,2,3,空}，表示无法安排这些任务。但是，当然有一种方法，只是因为它贪婪地选择了第二个任务的错误日期，所以没有找到它。 - Asad Saeeduddin

是的，有些棘手，还没有到位...需要想办法利用结束日期。谢谢。 - Ian Mercer

让我们在聊天中继续这个讨论。 - Ian Mercer

Answer 2

如果我错了，请纠正我，但我认为这类问题的名称应该是区间调度。

从您的帖子中，我假设您不是在寻找最佳时间表，而只是想在O(n)内找到任何解决方案。

问题在于排序需要O(nlogn)，计算也需要O(nlogn)。您可以尝试一步完成：

定义V-每个任务所需时间的向量。

定义P-在给定任务之前完成的任务的向量。 即如果任务2在任务3之前完成，则P[3]=2。

当然，正如您所看到的，主要计算涉及查找P[j]。您始终选择最后结束的非重叠任务。

因此，要找到P[i]。找到在第i个任务之前结束的任务。如果存在多个，则选择最后结束的任务。

定义M-包含结果插槽的向量。

算法： WIS(n)

M[0] <- 0
for j <- 1 to n
    do M[j] = max(wj + M[p(j)], M[j-1])
return M[n]

- JD009

---

如果找到 P 的复杂度大于常数时间，那么这不意味着你不能在 O(n) 中完成吗？ - Asad Saeeduddin

如果找到P的复杂度为O(n)，并且算法要求您计算{i...n}中的P_i，那么该算法如何也是O(n)？或者我是否误解了需要计算P的次数？ - Asad Saeeduddin

你只需要计算P一次。 - JD009

抱歉如果我有点迟钝，但我看不出你如何在常数时间内计算P[i]。你必须检查所有其他任务，这是O(n)，在P的n个索引上累积为O(n^2)。 - Asad Saeeduddin

我浏览了链接，但不确定你想让我参考哪里。作者正在解决一个完全不同的问题（区间调度最大化），动态规划解决方案的最终复杂度为O(n logn)。 - Asad Saeeduddin

Answer 3

按照结束日期和开始日期排序。然后仅按排序顺序处理数据，执行在开始日期之后的任务。

- jdweng

---

@Steve314 对于固定基数，基数排序的时间复杂度为O(dn)，其中d是输入中最大数字的位数。由于该问题没有保证开始日期的位数上限，因此这里的复杂度是不确定的。 - Asad Saeeduddin

@Asad - 天数为n，就我所见，天数范围是连续的。因此，日期数字始终在0..n-1范围内。每个日期的基数-n位数恰好为一。除了那一个重要的基数-n位数外，所有零位都是无关紧要的。这基本上是一个有n个桶的桶排序，但我们需要两次通过处理与基数排序相同的方式来处理两个日期，因此将每个日期视为一个数字。 - user180247

@Asad - 因为在给定的k进制下，j个数字中可以表示的最大整数是(k^j)-1。对数是幂的反函数。由于这是一个离散的情况，实际上有一个“ceiling”（天花板）的逆运算，但在渐近术语中，你只需说表示范围在0..n内的数字所需的k进制位数受log n的限制-也就是O(log n)。当然，k与n无关-基数n的位数仍为1。 - user180247

@Asad - 所以你是在假设，我并不是说你错了，我只是猜测也许情况并非如此。你不是OP，也不是指派OP解决问题的人。无论如何，正如我已经说过的，如果你假设n为0..infinity，那么仅在O(n)时间内读取所有n个任务的1个日期是不可能完成的。虽然我把O(n log n)理解错了 - 它不是一个上限，而是一个下限，因为根据鸽笼原理，O(log n)指的是日期中最小有效数字的数量。 - user180247

@Steve314 除非问题中给出了限制条件，否则我们不能假设这样的限制条件。这似乎只是遵循合理惯例。我的意思是，如果我可以做任何我想做的假设，那么荒谬的极端情况就是我会假设我们只处理一个空任务列表，并给出一个空列表作为解决方案。 - Asad Saeeduddin