2
$\begingroup$

I have such a task at university: we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+1$. We can perform at most 1 task at a time and we cannot interrupt performing it. Create an algorithm to check if it is possible to perform all the tasks. $b(i)$ and $e(i)$ may not be integers.

I have done some research online, but I haven't found anything concerning this problem.

Actually I think the following algorithm would work (I haven't found a counterexample yet):

iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

If this algorithm works, how could I prove it?

$\endgroup$
  • $\begingroup$ Have you tried a greedy approach similar to interval scheduling? $\endgroup$ – Yuval Filmus May 22 '18 at 18:04
  • $\begingroup$ @YuvalFilmus actually I think I have just come up with a similar algorithm and edited the question. Please check this out and tell me what You think. $\endgroup$ – Leftismer May 22 '18 at 18:17
  • $\begingroup$ Try to prove that it works, by mimicking the proof for interval scheduling. $\endgroup$ – Yuval Filmus May 22 '18 at 18:18
1
$\begingroup$

I have proved that my algorithm works, so here's the algorithm, just to remind:

Iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

And the proof follows:

Suppose the algorithm is not correct and there exist such data, that it returns false, while it is possible to perform a plan (mapping: task -> time) in which each task is performed.

Now let's find the first task (chronologically), which is performed at different time in plan created by my algorithm (further called my plan) and the optimal plan.

Then, this task is performed earlier in my plan (because of how the algorithm works) and this is the task we must most hurry with (compared to the rest of tasks performed later in my plan) (because of the order of tasks list processed by the algorithm).

So, we can safely reschedule this task (call it $t$) (in optimal plan) to the time when it is performed in my plan.

If this rescheduling bears any conflict with another task (call it $t'$) in the optimal plan, we can also safely move $t'$ to the time of, when $t$ was performed originally in the optimal plan (because $e(t) < e(t')$).

So we see that we can safely rearrange the optimal plan, so it becomes my plan. Hence my plan is optimal and the algorithm works.

$\endgroup$

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.