Maximum Number of Events That Can Be Attended II — Solution
Maximum Number of Events That Can Be Attended II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Events That Can Be Attended II is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Sorting, Binary Search
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
events[i] = [start, end, value] describes an event running from day start to day end inclusive, worth value. Attending an event means attending it in full, and you cannot attend two events that share any day — the next event must start strictly after the previous one ends.
Attend at most k events and return the maximum total value.
Example 1
Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Attend `[1,2,4]` and `[3,4,3]`.
Example 2
Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: The single event worth 10 beats any pair.
Example 3
Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Take the three most valuable.
Constraints
1 <= k <= events.length <= 10^61 <= k * events.length <= 10^61 <= starti <= endi <= 10^91 <= valuei <= 10^6
Hints for Maximum Number of Events That Can Be Attended II
Hint 1
Sort the events by start day, then the choice at each event is simply take or skip.
Hint 2
Taking event
ijumps to the first event starting afterend[i]— a binary search.Hint 3
dp[i][j]= the best value from eventionward using at mostjattendances.
How to solve Maximum Number of Events That Can Be Attended II
Sort by start day. For each event precompute nextFree[i], the index of the first event starting strictly after event i ends. Then dp[i][j] = max(dp[i+1][j], value[i] + dp[nextFree[i]][j-1]) — skip or take.
Approach
- Sort the events by start day.
- Binary-search each
nextFree[i]over the sorted starts. - Fill
dpbackwards overiand forwards overj, taking the better of skip and take. - Return
dp[0][k].
Why it works
Sorting by start is what makes nextFree a forward jump rather than a search over the whole set — every compatible successor lies in a contiguous suffix, so one binary search names the whole set of them. The j - 1 on the take branch is the attendance budget, which is why the DP needs two dimensions rather than the single one a plain weighted-interval-scheduling problem would use.
Complexity
- Time —
O(n log n + n · k) - Space —
O(n · k)
Pitfalls
- The events are inclusive at both ends, so the successor must start strictly after the end day.
- Sorting by end day instead makes the jump index wrong.
- At most
k— fewer is allowed, which the skip branch already covers.
Reference solution
Python
from bisect import bisect_right
from typing import List
def maxValue(events: List[List[int]], k: int) -> int:
events = sorted(events)
n = len(events)
starts = [e[0] for e in events]
next_free = [bisect_right(starts, e[1]) for e in events]
dp = [[0] * (k + 1) for _ in range(n + 1)]
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[next_free[i]][j - 1])
return dp[0][k]Java
public static int maxValue(int[][] events, int k) {
int[][] sorted = events.clone();
Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
int n = sorted.length;
int[] nextFree = new int[n];
for (int i = 0; i < n; i++) {
int lo = i + 1, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (sorted[mid][0] > sorted[i][1]) hi = mid;
else lo = mid + 1;
}
nextFree[i] = lo;
}
int[][] dp = new int[n + 1][k + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j <= k; j++) {
dp[i][j] = Math.max(dp[i + 1][j], sorted[i][2] + dp[nextFree[i]][j - 1]);
}
}
return dp[0][k];
}C++
int maxValue(vector<vector<int>>& events, int k) {
vector<vector<int>> sorted = events;
sort(sorted.begin(), sorted.end());
int n = (int) sorted.size();
vector<int> nextFree(n, n);
for (int i = 0; i < n; i++) {
int lo = i + 1, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (sorted[mid][0] > sorted[i][1]) hi = mid;
else lo = mid + 1;
}
nextFree[i] = lo;
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j <= k; j++) {
dp[i][j] = max(dp[i + 1][j], sorted[i][2] + dp[nextFree[i]][j - 1]);
}
}
return dp[0][k];
}JavaScript
var maxValue = function(events, k) {
var sorted = events.slice();
sorted.sort(function(a, b) { return a[0] - b[0]; });
var n = sorted.length, i, j;
var nextFree = [];
for (i = 0; i < n; i++) {
var lo = i + 1, hi = n;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (sorted[mid][0] > sorted[i][1]) hi = mid; else lo = mid + 1;
}
nextFree.push(lo);
}
var dp = [];
for (i = 0; i <= n; i++) {
var row = [];
for (j = 0; j <= k; j++) row.push(0);
dp.push(row);
}
for (i = n - 1; i >= 0; i--) {
for (j = 1; j <= k; j++) {
var skip = dp[i + 1][j];
var take = sorted[i][2] + dp[nextFree[i]][j - 1];
dp[i][j] = skip > take ? skip : take;
}
}
return dp[0][k];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming