# interval scheduling variant: 1 machine with 2 tasks need to complete only

I am looking for an optimal solution of an interval scheduling variant.

Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum and do not over lap (Equal start/end time counts as overlapping).

So if there are these task [9-14], [7-13],[1,4],[2-5],[2-10],[4-9]

The answer would be [1,4] and [7-13], whose execution time are 3+6=9 in total.

I can only think of an algorithm with n^2 complexity. That is the obvious solution of matching every period together, check if they overlap, and if they don't, replace a previously initialized Max value with their sum if it > Max. It does not seem to be optimal, as it does not pass the time test in my professor exercise.

So anyway, can anyone think of a more optimal solution?

Let $$max$$ be the maximum period of the tasks we have checked so far. Let $$max2$$ be the maximum sum of two non-overlapping tasks we have checked so far. Both of them are 0 initially.
• A start time is encountered. If the sum of the period of the corresponding task and $$max$$ is greater than $$max2$$, update $$max2$$.
• An end time is encountered. If the period of the corresponding task is greater than $$max$$, update $$max$$.
Now $$max2$$ is what we wanted. The algorithm runs in $$O(n\log n)$$.