Interval scheduling: Difference between revisions

Revision as of 04:57, 3 October 2023

Revision as of 05:05, 3 October 2023

Line 46:

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[];

// v[0] does not exist., Theand the first interval vector is setassigned to v[1].

w[0] = 0; p[0] = 0; M[0] = 0;

// The following code determines the value of M for each vector.

// The maximum weight of the schedule is equal to M[numOfVectors].

for (int i = 1; i < numOfVectornumOfVectors + 1; i++) {

M[i] = max(w[i] + M[p[i]], M[i - 1]);

}

// TheFunction maximumto weight ofconstruct the optimal schedule is equal to M[numOfVectors].

schedule (j) {

if (j == 0) { return; }