Content deleted Content added
m →Single-Interval Scheduling Maximization: reorganized to be better categorized Tags: Mobile edit Mobile app edit Android app edit |
→Weighted: Added example |
||
Line 53:
w[0] = 0; p[0] = 0; M[0] = 0;
// The following code determines the value of M for each vector.
for (int i = 1; i < numOfVector + 1; i++) {
M[i] = max(w[i] + M[p[i]], M[i - 1]);
}
// The maximum weight of the schedule is equal to M[numOfVectors
schedule (j) {
Line 67 ⟶ 68:
}
</syntaxhighlight><ref>{{Cite book |last1=Kleinberg |first1=Jon |title=Algorithm Design |last2=Tardos |first2=Eva |publisher=Pearson |year=2006 |isbn=9780321295354 |edition=1st |pages=254}}</ref>
==== Example ====
If we have the following 9 vectors sorted by finish time, with the weights above each corresponding interval, we can determine which of these vectors are included in our maximum weight schedule which only contains a subset of the following vectors.
[[File:Weighted Interval Scheduling Example.png|none|thumb|701x701px]]
Here, we start with our final vector (where j=9 in this example), and input it into our schedule function in the code block above. We perform these actions until j is set to 0, at which point, we only include into our final schedule the encountered intervals which met the <math display="inline">w[j]+M[p[j]] >= M[j-1]</math> requirement.
{| class="wikitable mw-collapsible"
|+
!j
!Calculation
!Is <math display="inline">w[j]+M[p[j]] >= M[j-1]</math>?
(i.e. Is this vector included in the final schedule)?
!Set j to
|-
|9
|<math>\begin{align} & w[j]+M[p[j]]=w[9]+M[p[9]]=5+M[6]=5+16=21 \\ &
M[j-1]=M[9-1]=M[8]=20
\end{align}</math>
|Yes
|j=p[j]=p[9]=6
|-
|6
|<math>\begin{align} & w[j]+M[p[j]]=w[6]+M[p[6]]=5+M[4]=5+11=16 \\ &
M[j-1]=M[6-1]=M[5]=11
\end{align}</math>
|Yes
|j=p[j]=p[6]=4
|-
|4
|<math>\begin{align} & w[j]+M[p[j]]=w[4]+M[p[4]]=3+M[1]=3+5=8 \\ &
M[j-1]=M[4-1]=M[3]=11 \\
\end{align}</math>
|No
|j=j-1=4-1=3
|-
|3
|<math>\begin{align} & w[j]+M[p[j]]=w[3]+M[p[3]]=6+M[1]=6+5=11 \\ &
M[j-1]=M[3-1]=M[2]=5
\end{align}</math>
|Yes
|j=p[j]=p[3]=1
|-
|1
|<math>\begin{align} & w[j]+M[p[j]]=w[1]+M[p[1]]=5+M[0]=5+0=5 \\ &
M[j-1]=M[1-1]=M[0]=0
\end{align}</math>
|Yes
|j=p[j]=p[1]=0
|}
==Group Interval Scheduling Decision==
| |||