Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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:
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.
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.
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|)$.
