Scheduling algorithm in linear complexity

Question

Here's the problem:

We have n tasks to complete in n days. We can complete a single task per day. Each task has a start date and an end date. We can't start a task before the start date and it has to be completed before the end date. So, given a vector s for the start dates and e for the end dates give a vector d, if it exists, where d[i] is the date you do task i. For example:

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 |
+--------+------------+----------+

We have as a possible solution:

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

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

It is trivial to create an algorithm with O(n^2). It is not too bad either to create an algorithm with O(nlogn). There is supposedly an algorithm that gives a solution with O(n). What would that be?

Answer 1

When you can't use time, use space! You can represent the tasks open on any day using a bit vector. In O(n) create a "starting today" array. You can also represent the tasks ending soonest using another bit vector that can also be calculated in O(n). And then finally, in O(n) again scan each day, adding in any tasks starting that day, picking the lowest numbered task open that day giving priority to the ones ending soonest.

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));
    }
}

Result in this case is: 1, 4, 2, 3, 0 as expected.