Maximum Number of Events That Can Be Attended II
Maximum Number of Events That Can Be Attended II is a hard dynamic programming problem solved with the 2d dp pattern.
The best approach, optimal (bottom-up dp + binary search), runs in O(n log n + n · k) time and O(n · k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (pick or skip every event) up.
Problem
You are given an array events where events[i] = [startDay, endDay, value]: the i-th event runs from startDay to endDay, both days included, and attending it earns value. You may attend at most k events.
You can only be at one event at a time, and you must attend an event for its whole duration. That means two chosen events may not share any day: if one ends on day d, the next one must start on day d + 1 or later.
Return the maximum total value you can earn.
Examples
Example 1
- Input
events = [[1,3,5],[2,5,9],[4,6,4],[7,8,3]], k = 2- Output
12- Why
- Attend [2,5,9] and [7,8,3] for 9 + 3 = 12. Taking [1,3,5] and [4,6,4] gives only 9.
Example 2
- Input
events = [[1,4,6],[4,5,8],[6,9,2]], k = 3- Output
10- Why
- [1,4] and [4,5] share day 4, so they cannot both be attended. The best is [4,5,8] + [6,9,2] = 10.
Example 3
- Input
events = [[1,1,3],[2,2,1],[3,3,7],[1,3,10]], k = 1- Output
10- Why
- With only one event allowed, pick the single most valuable one.
Constraints
1 <= k <= events.length1 <= k · events.length <= 10^61 <= startDay <= endDay <= 10^91 <= value <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (pick or skip every event) | O(2^n · n) | O(n) |
| Optimal (bottom-up DP + binary search) | O(n log n + n · k) | O(n · k) |
1Brute force (pick or skip every event)
O(2^n · n)Each event can be taken or skipped, and every take does a linear scan.O(n)Recursion depth is at most n.Sort events by start day and recursively decide for each event whether to skip it or attend it. Attending one jumps to the first later event that starts after it ends and uses up one of the k slots. The recursion tries every valid selection, so it is exponential.
- Sort events by start day.
- solve(i, left): if i == n or left == 0 return 0.
- skip = solve(i + 1, left).
- Scan forward from i + 1 to the first event whose start > events[i].end, call it nx; take = value + solve(nx, left - 1).
- Return max(skip, take).
class Solution {
public int maxValue(int[][] events, int k) {
Arrays.sort(events, (x, y) -> Integer.compare(x[0], y[0]));
return solve(events, 0, k);
}
private int solve(int[][] ev, int i, int left) {
if (i == ev.length || left == 0) return 0;
int skip = solve(ev, i + 1, left);
int nx = i + 1;
while (nx < ev.length && ev[nx][0] <= ev[i][1]) nx++;
int take = ev[i][2] + solve(ev, nx, left - 1);
return Math.max(skip, take);
}
}class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
ev = sorted(events, key=lambda e: e[0])
n = len(ev)
def solve(i: int, left: int) -> int:
if i == n or left == 0:
return 0
skip = solve(i + 1, left)
nx = i + 1
while nx < n and ev[nx][0] <= ev[i][1]:
nx += 1
take = ev[i][2] + solve(nx, left - 1)
return max(skip, take)
return solve(0, k)class Solution {
int solve(vector<vector<int>>& ev, int i, int left) {
if (i == (int)ev.size() || left == 0) return 0;
int skip = solve(ev, i + 1, left);
int nx = i + 1;
while (nx < (int)ev.size() && ev[nx][0] <= ev[i][1]) nx++;
int take = ev[i][2] + solve(ev, nx, left - 1);
return max(skip, take);
}
public:
int maxValue(vector<vector<int>>& events, int k) {
sort(events.begin(), events.end(), [](const vector<int>& x, const vector<int>& y) { return x[0] < y[0]; });
return solve(events, 0, k);
}
};function maxValue(events, k) {
const ev = [...events].sort((x, y) => x[0] - y[0]);
const n = ev.length;
const solve = (i, left) => {
if (i === n || left === 0) return 0;
const skip = solve(i + 1, left);
let nx = i + 1;
while (nx < n && ev[nx][0] <= ev[i][1]) nx++;
const take = ev[i][2] + solve(nx, left - 1);
return Math.max(skip, take);
};
return solve(0, k);
}2Optimal (bottom-up DP + binary search)
O(n log n + n · k)Sorting and n binary searches cost O(n log n); the table has (n + 1)(k + 1) cells, each filled in O(1).O(n · k)The DP table, which the constraint n · k <= 10^6 keeps small.The brute force recomputes the same (i, left) states many times. Store them in a table instead: dp[i][j] is the best total using only events i..n-1 with at most j attendances. Fill it from the last event backwards, and find each event's next compatible index once with binary search over the sorted start days.
- Sort events by start day and copy the start days into an array.
- For each i, binary-search nx[i] = the first index whose start > events[i].end.
- dp[n][j] = 0 and dp[i][0] = 0.
- For i from n - 1 down to 0 and j from 1 to k: dp[i][j] = max(dp[i + 1][j], value_i + dp[nx[i]][j - 1]).
- Return dp[0][k].
class Solution {
public int maxValue(int[][] events, int k) {
int n = events.length;
Arrays.sort(events, (x, y) -> Integer.compare(x[0], y[0]));
int[] starts = new int[n];
for (int i = 0; i < n; i++) starts[i] = events[i][0];
int w = k + 1;
int[] dp = new int[(n + 1) * w];
for (int i = n - 1; i >= 0; i--) {
int lo = i + 1, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (starts[mid] <= events[i][1]) lo = mid + 1;
else hi = mid;
}
int nx = lo, v = events[i][2];
for (int j = 1; j <= k; j++) {
dp[i * w + j] = Math.max(dp[(i + 1) * w + j], v + dp[nx * w + j - 1]);
}
}
return dp[k];
}
}class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
ev = sorted(events, key=lambda e: e[0])
n = len(ev)
starts = [e[0] for e in ev]
last_row = [0] * (k + 1) # dp row for index n
rows = [None] * (n + 1)
rows[n] = last_row
for i in range(n - 1, -1, -1):
nx = bisect.bisect_right(starts, ev[i][1], i + 1)
v = ev[i][2]
below = rows[i + 1]
jump = rows[nx]
row = [0] * (k + 1)
for j in range(1, k + 1):
a = below[j]
b = v + jump[j - 1]
row[j] = a if a > b else b
rows[i] = row
return rows[0][k]class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
int n = events.size();
sort(events.begin(), events.end(), [](const vector<int>& x, const vector<int>& y) { return x[0] < y[0]; });
vector<int> starts(n);
for (int i = 0; i < n; i++) starts[i] = events[i][0];
int w = k + 1;
vector<int> dp((size_t)(n + 1) * w, 0);
for (int i = n - 1; i >= 0; i--) {
int nx = upper_bound(starts.begin() + i + 1, starts.end(), events[i][1]) - starts.begin();
int v = events[i][2];
for (int j = 1; j <= k; j++) {
dp[(size_t)i * w + j] = max(dp[(size_t)(i + 1) * w + j], v + dp[(size_t)nx * w + j - 1]);
}
}
return dp[k];
}
};function maxValue(events, k) {
const ev = [...events].sort((x, y) => x[0] - y[0]);
const n = ev.length;
const starts = ev.map((e) => e[0]);
const w = k + 1;
const dp = new Int32Array((n + 1) * w);
for (let i = n - 1; i >= 0; i--) {
let lo = i + 1, hi = n;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (starts[mid] <= ev[i][1]) lo = mid + 1;
else hi = mid;
}
const nx = lo, v = ev[i][2];
for (let j = 1; j <= k; j++) {
dp[i * w + j] = Math.max(dp[(i + 1) * w + j], v + dp[nx * w + j - 1]);
}
}
return dp[k];
}Edge cases to test
- One event ending on the same day another starts (they overlap)
- k larger than the number of events that can fit together
- k = 1, where the answer is just the largest value
- A long, valuable event competing with several short ones
Hints
Hint 1
Sort the events by start day. For each event you either skip it or attend it; if you attend it, the next event you may consider is the first one starting after it ends.
Hint 2
The state is (index of the next event to consider, how many events you may still attend). That is at most n · k states.
Hint 3
Binary search on the sorted start days finds the next compatible event in O(log n).
FAQ
What is the best time complexity for Maximum Number of Events That Can Be Attended II?
Optimal (bottom-up DP + binary search) runs in O(n log n + n · k) time and O(n · k) extra space. Sorting and n binary searches cost O(n log n); the table has (n + 1)(k + 1) cells, each filled in O(1).
Which pattern does Maximum Number of Events That Can Be Attended II use?
It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.
Is there a brute force solution for Maximum Number of Events That Can Be Attended II?
Yes. Brute force (pick or skip every event) takes O(2^n · n) time and O(n) space. Sort events by start day and recursively decide for each event whether to skip it or attend it.
Which edge cases should I test for Maximum Number of Events That Can Be Attended II?
One event ending on the same day another starts (they overlap); k larger than the number of events that can fit together; k = 1, where the answer is just the largest value; A long, valuable event competing with several short ones.