Maximum Number of Events That Can Be Attended II
Asked at Snowflake
Problem
Maximum Number of Events That Can Be Attended II gives you events with a start day, end day, and value. You can attend at most k events, must attend each for its whole duration, and cannot attend overlapping events (an event ending on day d blocks another starting on day d). Maximize the total value. It is weighted interval scheduling with an extra dimension for the count.
Asked At
| Company | Difficulty | |
|---|---|---|
| Snowflake | Hard | View all Snowflake questions → |
How to Think About It
Without the k limit this is Maximum Profit in Job Scheduling. The limit adds a second DP dimension.
Sort events by start day. For each event i, precompute nxt[i] — the first event whose start is strictly after event i ends (binary search on starts).
Key insight: dp[i][j] = the best value using events i..n-1 with at most j events left. Either skip event i (dp[i+1][j]) or attend it (value[i] + dp[nxt[i]][j-1]).
Fill the table from i = n - 1 down to 0 so that dp[i+1] and dp[nxt[i]] are ready.
The constraint k * n <= 10^6 tells you the O(n * k) table is the intended size.
Optimal Approach
Step 1: Sort events by start; starts = list of start days.
Step 2: nxt[i] = bisect_right(starts, end_i).
Step 3: dp is an (n+1) x (k+1) table of zeros.
Step 4: 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[nxt[i]][j-1]).
Step 5: Return dp[0][k].
Time: O(n log n + n * k). Space: O(n * k).
What Trips People Up in Real Interviews
Using bisect_left on the end day. Events that start on the same day another ends overlap here, so the next event must start strictly later.
Ignoring k and solving the unlimited version.
Memoized recursion in Python over 10^6 states can hit recursion limits — prefer the bottom-up table.
Greedy by value or by end time. Neither handles the value/count trade-off.
Solution Code
from bisect import bisect_right
def maxValue(events, k):
events.sort()
n = len(events)
starts = [e[0] for e in events]
nxt = [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):
v = events[i][2]
row, skip, take = dp[i], dp[i + 1], dp[nxt[i]]
for j in range(1, k + 1):
row[j] = max(skip[j], v + take[j - 1])
return dp[0][k]Frequently Asked Questions
What is the Maximum Number of Events That Can Be Attended II problem?
Maximum Number of Events That Can Be Attended II gives you events with a start day, end day, and value. You can attend at most `k` events, must attend each for its whole duration, and cannot attend overlapping events (an event ending on day `d` blocks another starting on day `d`). Maximize the total value. It is weighted interval scheduling with an extra dimension for the count.
How do you solve Maximum Number of Events That Can Be Attended II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Number of Events That Can Be Attended II?
Maximum Number of Events That Can Be Attended II is asked at Snowflake. It is a hard difficulty problem.
What are common mistakes on Maximum Number of Events That Can Be Attended II?
- Using `bisect_left` on the end day. Events that start on the same day another ends overlap here, so the next event must start strictly later.
- Ignoring `k` and solving the unlimited version.
- Memoized recursion in Python over `10^6` states can hit recursion limits — prefer the bottom-up table.
- Greedy by value or by end time. Neither handles the value/count trade-off.