Content deleted Content added
No edit summary |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
Line 39:
=== Weighted ===
Problems involving weighted interval scheduling are equivalent to finding a maximum-weight [[Independent set (graph theory)|independent set]] in an [[interval graph]]. Such 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 |issn=0004-5411 |s2cid=12329294|url-access=subscription }}</ref>
Assuming the vectors are sorted from earliest to latest finish time, the following pseudocode determines the maximum weight of a single-interval schedule in Θ(n) time:<syntaxhighlight line="1" lang="c">
| |||