algorithm - 线性复杂度的调度算法

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) 的解决方案。那会是什么？

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，如预期。