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?