1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.