Interval scheduling: Difference between revisions

Revision as of 06:48, 12 July 2021

Revision as of 19:37, 13 July 2021

Line 24:

* Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.

* Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.

The following [[greedy algorithm]], called [[Earliest deadline first scheduling]], does find the optimal solution for unweighted single-intevalinterval scheduling:

# Select the interval, ''x'', with the earliest '''finishing time'''.

# Remove ''x'', and all intervals intersecting ''x'', from the set of candidate intervals.