A greedy algorithm can efficiently solve unweighted interval scheduling, but when the intervals are weighted it fails: the greedy algorithm may choose a task that precludes a later, heavily weighted task. We can solve this without resorting to BFI by limited backtracking: again go through the list by order of finish time, but now instead of committing to schedule available tasks recursively consider the remaining possibilities conditional on including and excluding it, including it if its weight plus the aggregate weight of the former exceed the aggregate weight of the latter. A naive interpretation gives exponential runtime, but by memoizing the partial results one can reduce it to O(n) (aside from the recursive call, the computation is constant, and there can be no more than one recursive call made per task after memoizing. Finding not only the value but the solution efficiently requires a scan through the array of intermediate results.

No questions.

No comments.

No complaints.

This solution can be expressed not only as a recursive calculation with memoization but also as iteration over subproblems. Instead of recursively solving the subproblems as needed, start with the last