Maximum Number of Events That Can Be Attended II
Problem
Pick at most k of n events with start/end/value so no two overlap (any shared day disallowed); maximize total value.
events = [[1,2,4],[3,4,3],[2,3,1]], k = 27from bisect import bisect_left
def max_value(events, k):
events.sort(key=lambda e: e[1])
n = len(events)
starts = [e[0] for e in events]
# for each i, next_idx = smallest j with events[j][0] > events[i][1]
nxt = [bisect_left(starts, events[i][1] + 1) for i in range(n)]
dp = [[0] * (k + 1) for _ in range(n + 1)]
# iterate i from n-1 down
for i in range(n - 1, -1, -1):
for j in range(1, k + 1):
dp[i][j] = max(dp[i+1][j], events[i][2] + dp[nxt[i]][j-1])
return dp[0][k]function maxValue(events, k) {
events.sort((a, b) => a[1] - b[1]);
const n = events.length;
const starts = events.map(e => e[0]);
function bsl(t) { let lo = 0, hi = n; while (lo < hi) { const m = (lo + hi) >> 1; if (starts[m] < t) lo = m + 1; else hi = m; } return lo; }
const dp = Array.from({length: n + 1}, () => new Array(k + 1).fill(0));
for (let i = n - 1; i >= 0; i--) {
const nxt = bsl(events[i][1] + 1);
for (let j = 1; j <= k; j++) {
dp[i][j] = Math.max(dp[i+1][j], events[i][2] + dp[nxt][j-1]);
}
}
return dp[0][k];
}class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, (a, b) -> a[1] - b[1]);
int n = events.length;
int[] starts = new int[n]; for (int i = 0; i < n; i++) starts[i] = events[i][0];
int[][] dp = new int[n + 1][k + 1];
for (int i = n - 1; i >= 0; i--) {
int t = events[i][1] + 1, lo = 0, hi = n;
while (lo < hi) { int m = (lo + hi) >> 1; if (starts[m] < t) lo = m + 1; else hi = m; }
for (int j = 1; j <= k; j++)
dp[i][j] = Math.max(dp[i+1][j], events[i][2] + dp[lo][j-1]);
}
return dp[0][k];
}
}int maxValue(vector<vector<int>>& events, int k) {
sort(events.begin(), events.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
int n = events.size();
vector<int> starts(n); for (int i = 0; i < n; i++) starts[i] = events[i][0];
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
for (int i = n - 1; i >= 0; i--) {
int t = events[i][1] + 1, lo = 0, hi = n;
while (lo < hi) { int m = (lo + hi) >> 1; if (starts[m] < t) lo = m + 1; else hi = m; }
for (int j = 1; j <= k; j++)
dp[i][j] = max(dp[i+1][j], events[i][2] + dp[lo][j-1]);
}
return dp[0][k];
}Explanation
We may attend at most k non-overlapping events and want the highest total value. This is a "pick or skip" problem, and the cleanest way to handle the no-overlap rule is to sort events by end day first.
We define dp[i][j] as the best value using events from index i onward when we may still attend j more. For each event we have two choices: skip it and take dp[i+1][j], or attend it, earning its value plus the best from the next event that doesn't overlap, with one fewer slot: events[i][2] + dp[nxt][j-1].
The tricky part is finding nxt: the first event whose start day is strictly after the current event's end day. Since starts are sorted, a binary search finds it in log time, which lets us jump past every conflicting event at once.
We fill the table from the last event backward so the future answers (dp[i+1] and dp[nxt]) are ready, and the final answer is dp[0][k]. Taking the max of skip vs attend at every cell guarantees the optimal combination.
Example: for [[1,2,4],[3,4,3],[2,3,1]] with k = 2, attending [1,2] (value 4) then the non-overlapping [3,4] (value 3) yields 7.