Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
