Content deleted Content added
Tags: Mobile edit Mobile app edit Android app edit |
→Weighted: I gave pseudocode to solve the weighted interval scheduling problem. |
||
Line 39:
=== Weighted ===
When the intervals have weights, the problem is equivalent to finding a maximum-weight [[Independent set (graph theory)|independent set]] in an [[interval graph]]. It can be solved in polynomial time.<ref name=":0">{{Cite journal|last=Bar-Noy|first=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}}</ref>
To find the maximum weight of a single interval schedule in Θ(n) time, perform the following pseudocode:<syntaxhighlight line="1">
// The vectors are already sorted from earliest to latest finish time.
int v[numOfVectors+1]; //list of interval vectors
int w[numOfVectors+1]; //w[j] is the weight for v[j].
int p[numOfVectors+1]; //p[j] is the # of vectors that end before v[j] begins.
int M[numOfVectors+1];
int finalSchedule[numOfVectors];
//v[0] does not exist. The first interval vector is set to v[1].
w0[0]=0; p[0]=0; M[0]=0;
for(int i = 0; i < numOfVectors; i++){
M[i] = max(w[i]+M[p[i]], M[i-1]);
}
//The maximum weight of the schedule is equal to M[numOfVectors].
int index = numOfVectors-1;
schedule(j){
if(j==0){return;}
elif(w[j]+M[p[j]] >= M[j-1]){
//add v[j] to schedule.
finalSchedule[index] = v[j];
index--;
schedule(p[j]);
} else {schedule(j-1);}
}
</syntaxhighlight>
==Group Interval Scheduling Decision==
| |||