Most Credits With at Most K Classes
Each class is [start, end, credits]. Pick classes that do not overlap — a class may start exactly when another ends — and take at most k of them, so that the total credits are as large as possible. Return that total.
maxCredits([[0, 2, 3], [1, 3, 4], [2, 4, 5]], 1) -> 5 maxCredits([[0, 2, 3], [1, 3, 4], [2, 4, 5]], 2) -> 8 // [0, 2] and [2, 4]
Hints
Hint 1
Sort by end time. For each class, binary-search the last class that ends at or before its start — the latest compatible predecessor.
Hint 2
dp[i][j] = best credits using the first i classes with at most j picks: skip class i, or take it and add dp[predecessor][j − 1].