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?

  • 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
    Commented Aug 22, 2017 at 1:17

1 Answer 1


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.

  • 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$ Commented Aug 22, 2017 at 13:44
  • $\begingroup$ @j_random_hacker I will happily apply that edit. Nice catch. $\endgroup$
    – mm8511
    Commented Aug 22, 2017 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.