Interval scheduling: Difference between revisions

Revision as of 05:05, 3 October 2023

Revision as of 06:36, 4 October 2023

Line 71:

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.png|none|thumb|872x872px]]

Here, we input our final vector (where j=9 in this example) into our schedule function from the code block above. We perform the actions in the table below 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]] >=\ge M[j-1]</math> requirement. This final schedule is the schedule with the maximum weight.

{| class="wikitable"

!j

!Calculation

!<math display="inline">w[j]+M[p[j]] >=\ge M[j-1]</math>

(i.e. This vector is included in the final schedule)

!Set j to