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

Question

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?

Answer 1

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.

Sort all start times and end times of the given tasks. Iterate over them, from the smallest to largest.

• 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)$.

The above algorithm does not specify what to do when multiple times are encountered at the same time. That part should be easy for you to fill in.