Earliest finish collects 4 from two short appointments. Taking the long appointment collects 10. The previous proof preserved the number of appointments, which is no longer the requested objective.

Sort appointments by start time. best(i) is the maximum reward among appointments from index i onward. Skipping leads to i+1; taking earns its reward and jumps to the first start time at least its end.

from bisect import bisect_left
from functools import cache

def max_reward(appointments):
    jobs = sorted(appointments)
    starts = [job[0] for job in jobs]
    following = [bisect_left(starts, end, lo=i + 1)
                 for i, (_, end, _) in enumerate(jobs)]
    @cache
    def best(i):
        if i == len(jobs):
            return 0
        return max(best(i + 1), jobs[i][2] + best(following[i]))
    return best(0)

assert max_reward([(0, 2, 2), (2, 4, 2), (0, 4, 10)]) == 10
assert max_reward([(0, 2, 7), (2, 4, 8)]) == 15
assert max_reward([]) == 0

Assume positive duration and half-open intervals; choosing none is permitted. Because starts are sorted, compatibility has a false-then-true boundary, making binary search valid. The recursive dependencies always go to larger indices.

Sorting and successor lookup take O(n log n); the DP evaluates O(n) states with two choices each. Storage is O(n), including cache and stack. A reverse-index table avoids deep recursion.

The state needs only one coordinate: after taking an interval, the jump removes incompatible early starts. You could instead write a state involving current time, but that is not required by this formulation.

Analogy limit: the word “interval” in the story does not mean the algorithm is interval DP. Here the state is a suffix index; interval DP will describe a subproblem bounded by two positions.

No. It permits the empty selection with value zero. Track whether a required selection has occurred, or otherwise enforce a nonempty result with suitable feasible and impossible base cases.