Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit
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) &lt; 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.