1
$\begingroup$

In interval scheduling, the greedy solution which maximizes the schedule that contains the largest number of "compliant intervals" involves initially sorting the list of intervals in ascending order by the end-times/point of each interval.

What confuses me, is if two or more intervals have the same ending time.

When performing the initial sort, should one base the sort of the sub-range of intervals on start time?

and if so should it be in ascending or descending order?

$\endgroup$
  • 2
    $\begingroup$ If two intervals have the same ending time, you can sort them however you like; you'll get the same answer both ways (the proof that the greedy solution works makes this clear). $\endgroup$ – jschnei Aug 22 '17 at 1:17
1
$\begingroup$

The greedy algorithm can be characterized as follows:

Let $I$ be the initial set of intervals

1) Select an interval, $x \in I$, with the earliest finishing time.

2) Remove $x$ and all intervals intersecting $x$ from $I$, obtaining $I^{'}$.

3) add $x$ to the solution

4) Set $I=I^{'}$

5) Continue until $I$ is empty.

Here, $x$ is some remaining interval that finishes before all other intervals in $I$. When we add $x$ to our solution we have already removed any interval with the same finish time as $x$ that may have had a start time which was "too early." If there is some other $y\in I$ with the same finish time as $x$ that is present when $x$ is chosen, then by necessity, both $x$ and $y$ begin after the last interval we added to our solution, so either is a legitimate choice.

$\endgroup$
  • 1
    $\begingroup$ Can I suggest changing "Select the interval" to "Select an interval"? I would also emphasise that the state (the number of selected-so-far intervals, and the set of remaining intervals) will be identical after choosing any interval having minimum end time. $\endgroup$ – j_random_hacker Aug 22 '17 at 13:44
  • $\begingroup$ @j_random_hacker I will happily apply that edit. Nice catch. $\endgroup$ – mm8511 Aug 22 '17 at 16:28

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.