Content deleted Content added
Citation bot (talk | contribs) Add: publisher. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1605/2500 |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{short description|Class of problems in
'''Interval scheduling''' is a class of problems in [[computer science]], particularly in the area of [[algorithm]] design. The problems consider a set of tasks. Each task is represented by an ''interval'' describing the time in which it needs to be processed by some machine (or, equivalently, scheduled on some resource). For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is ''compatible'' if no two intervals overlap on the machine/resource. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.
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">
Line 197:
{{Scheduling problems}}
[[Category:Optimal scheduling]]
[[Category:NP-complete problems]]
| |||