Interval scheduling: Difference between revisions

Revision as of 02:24, 2 October 2023

Revision as of 04:57, 2 October 2023

Line 21:

==Single-Interval Scheduling Maximization==

Single-interval scheduling refers to creating an interval schedule in which no intervals overlap.

=== Unweighted ===

Line 38 ⟶ 39:

=== Weighted ===

When the intervals have weights, the interval scheduling problem is equivalent to finding a maximum-weight [[Independent set (graph theory)|independent set]] in an [[interval graph]]. ItThese weighted interval scheduling problems can be solved in polynomial time.<ref name=":0">{{Cite journal|last1=Bar-Noy|first1=Amotz|last2=Bar-Yehuda|first2=Reuven|last3=Freund|first3=Ari|last4=(Seffi) Naor|first4=Joseph|last5=Schieber|first5=Baruch|author5-link=Baruch Schieber|date=2001-09-01|title=A unified approach to approximating resource allocation and scheduling|url=https://doi.org/10.1145/502102.502107|journal=Journal of the ACM|volume=48|issue=5|pages=1069–1090|doi=10.1145/502102.502107|s2cid=12329294 |issn=0004-5411}}</ref>

To find the maximum weight of a single -interval schedule (i.e. an interval schedule in which no intervals overlap) in Θ(n) time, perform the following pseudocode:

<syntaxhighlight line="1" lang="c">

// The vectors are already sorted from earliest to latest finish time.