Content deleted Content added
→Weighted: Added example |
→Weighted: clarified conclusion of example |
||
Line 72:
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. This final schedule is the schedule with the maximum weight.
{| class="wikitable mw-collapsible"
|+
!j
!Calculation
!
(i.e.
!Set j to
|-
Line 85:
M[j-1]=M[9-1]=M[8]=20
\end{align}</math>
|True
|j=p[j]=p[9]=6
|-
Line 92:
M[j-1]=M[6-1]=M[5]=11
\end{align}</math>
|True
|j=p[j]=p[6]=4
|-
Line 99:
M[j-1]=M[4-1]=M[3]=11 \\
\end{align}</math>
|False
|j=j-1=4-1=3
|-
Line 106:
M[j-1]=M[3-1]=M[2]=5
\end{align}</math>
|True
|j=p[j]=p[3]=1
|-
Line 113:
M[j-1]=M[1-1]=M[0]=0
\end{align}</math>
|True
|j=p[j]=p[1]=0
|}
| |||