Jobs are given as (start, finish, weight): (1,3,4), (2,5,6), (4,6,5), (6,7,3), (5,8,8). No two chosen jobs may overlap. Compute the maximum total weight, name the chosen jobs, and give the complexity of the algorithm you used.

Jobs are given as (start, finish, weight): (1,3,4), (2,5,6), (4,6,5), (6,7,3), (5,8,8). No two chosen jobs may overlap. Compute the maximum total weight, name the chosen jobs, and give the complexity of the algorithm you used.

Approach: Sort by finish time, define p(j) as the last job that ends no later than job j starts, and write the recurrence over take or skip.

14, taking (2,5,6) and (5,8,8). Sort by finish time to get A(1,3,4), B(2,5,6), C(4,6,5), D(6,7,3), E(5,8,8) and let OPT(j) = max(w_j + OPT(p(j)), OPT(j-1)) where the predecessor p(j) is the last job finishing no later than job j starts. Then p(A) and p(B) are empty, p(C) = A, p(D) = C and p(E) = B. Evaluating gives OPT(A) = 4, OPT(B) = max(6, 4) = 6, OPT(C) = max(5 + 4, 6) = 9, OPT(D) = max(3 + 9, 9) = 12 and OPT(E) = max(8 + 6, 12), which is 14. Reading the choices back shows E taken with B, since B ends at 5 and E starts at 5. Sorting is O(n log n), each p(j) is one binary search over the finish times at O(log n), and the table fills in O(n), so the whole algorithm is O(n log n). The unweighted version is solved greedily by earliest finish time, and that greedy fails once weights differ, as taking A, C and D here gives only 12.

Follow-up: How does the recurrence change when you may run two jobs at once on two machines?

Key concepts: weighted interval scheduling, finish time, predecessor, binary search.