0
$\begingroup$

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered.

Here is an example:

enter image description here

Is there an algorithm that can solve this problem with a worst case efficiency of $O(n)$ where $n$ is the number of tasks and days.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Could you please credit the source of the problem? Proper attribution helps people answer your question. $\endgroup$ – Apass.Jack Apr 19 at 11:35
  • $\begingroup$ It's a school assignement. $\endgroup$ – Shanksme Apr 20 at 10:31
  • $\begingroup$ Hm, it looks like there is an $O(n)$ algorithm. $\endgroup$ – Apass.Jack Apr 20 at 16:18
  • $\begingroup$ Really ? Can you tell me what it is ? $\endgroup$ – Shanksme Apr 20 at 16:22
0
$\begingroup$

The more general version of your problem is the scheduling problem where we have $n$ independent tasks, each with an arrival time, a resource requirement (time), and a deadline. We define the Earliest Deadline First algorithm such that at every timepoint, we choose to process the task with the nearest deadline. While time is continuous, it is trivial to see that we can discretize time to be all points at which a task finishes or a new task arrives.

It is known that EDF is an optimal uniprocessor scheduling algorithm i.e. if there is a feasible schedule, EDF will find it and if EDF does not find a feasible schedule, then no feasible schedule exists. [1], [2]. However, this is not linear time if we aren't guaranteed an ordering of the deadlines of the arriving tasks. Let's use a priority queue to represent the waiting tasks. At every time point, which there are $O(n)$ of, we must insert and/or pull the next task from a priority queue sorted on deadlines. Each insertion is $O(\log n)$ time, thus resulting in $O(n\log n)$ time.

If your input was sorted by arrival, we could easily find whether or not there is a valid schedule by following the algorithm above, iterating through the days, adding tasks for that day to a priority queue and selecting the task with the nearest deadline from the queue. We fail if we ever try to assign a task to a day on or past its deadline.

As mentioned in the comments, we can sort the input by arrival time in linear time using counting sort or pigeonhole sort. The issue then is to somehow make the priority queue also linear time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You can't find whether or not there is a valid schedule by iteratively assigning tasks if the input was sorted by deadline. Here is an exemple where it doesn't work: {Task #0: s:2 e:3},{Task #1: s:2 e:3},{Task #2: s:1 e:4},{Task #3: s:1 e:4},{Task #4: s:0 e:5},{Task #5: s:0 e:5}. Also, it is possible to sort the tasks by deadline (or start time) with an efficiency of Θ(n) this way: initialize a vector V of vectors of integers of size n, then iterate tasks and push back each task in V[i] where i is the deadline of the task. Iterate over vectors of V starting from V[0] to get your tasks sorted. $\endgroup$ – Shanksme Apr 20 at 10:29
  • $\begingroup$ This works well but you have to take in account that the sorted order of starts is not the same than deadlines one. Thus, you need two heap queues in the general case. One sorted on increasing starts that unstack on the other on each time step (when current time passes start time). The other is indeed on deadline increasing and let know the next task to schedule on each time step. $\endgroup$ – Vince Apr 20 at 13:35
  • $\begingroup$ Yes you are right, I should have said you sort by arrival date (after all that’s how the algorithm works). If you sort by start date, and use preemption based off of due date, it will work in your examples and all others. With respect to the sorting, you are also right! I’ll update my answer. $\endgroup$ – Bryce Kille Apr 20 at 13:39
  • $\begingroup$ @Shanksme as Vince mentioned, we need two things to be sorted. While I agree that we can use a linear time sort on arrival time, I am not quite sure how we could know, at each day, what remaining task has the nearest deadline. Do you have any ideas? $\endgroup$ – Bryce Kille Apr 20 at 13:52
-1
$\begingroup$

As each task has the atomic time step as duration, you can consider your scheduling problem as an assignment problem :

You have N tasks and N days and have to assign each task a day. Just consider a bipartite graph with N "task" nodes on a side and N "days" tasks on the other. There are edges between a task and a day when assignement is possible ($start \le day \le deadline$). The problem is now to select exactly N edges with one per task and one per day.

Then the best is probably to use an Hopcroft-Karp algorithm to look for the maximum cardinality assignment. If a perfect solution exists, it would be found else the number of "lost" task would be minimized.

This algorithm is $O(|E|\sqrt N)$ with $E$ the set of edges in the bipartite graph. If the time slots of the tasks are short with respect to the whole time horizon ($deadline - start \ll N$), then this algorithm is near-linear in the number of edges $O(|E|)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @Apass.Jack You are right, I totally confused $V$ and $E$ here, I correct it, thank you. $\endgroup$ – Vince Apr 19 at 14:42
  • 1
    $\begingroup$ @Apass.Jack about the need of proper attribution, I totally understand your point of view and CS policy on it. On the other hand, this is a school case and I do not expect any clear "propery" behind. But well I will be more patient before posting answers. $\endgroup$ – Vince Apr 19 at 14:49
  • 1
    $\begingroup$ Let $deadline-start=c$ for all tasks. Then $|E|=Nc$. $|V|=2N$. Then $|E|\sqrt{|V|}=\sqrt 2cN^{1.5}$. Suppose $c$ is a constant. Then $O(|E|{\sqrt {|V|}})=O(|E|^{1.5})$. Is that case part of what you meant by "near-linear in the number of edges"? $\endgroup$ – Apass.Jack Apr 19 at 15:09
  • $\begingroup$ While I agree that the time complexity of $O(|E|\sqrt{N})$ and near linear I’m the edges if we have a sparse bipartite graph, I don’t think that answers the question since it’s possible to have a dense graph, in which case the runtime could be $O(N^{2.5}$, right? $\endgroup$ – Bryce Kille Apr 19 at 17:06
  • $\begingroup$ @Apass.Jack In fact I just copied the wikipedia line on it. But I realise there is no big-O in it... They probably talk about amortized time. Below they mention that it would be O(|E| log |V|) for a random sparse graph. $\endgroup$ – Vince Apr 19 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.