Maximum Number of Events That Can Be Attended II

Maximum Number of Events That Can Be Attended II

What is this problem about?

The Maximum Number of Events That Can Be Attended II coding problem extends the previous version: now you can attend at most k events (instead of one per day), and each event has a value. You still attend each event on exactly one day within its range, attending at most one event per day. Maximize the total value of events attended. This is a harder variant combining DP with binary search.

Why is this asked in interviews?

Microsoft, Google, Amazon, Bloomberg, General Electric, and Snowflake include this problem because it combines dynamic programming with binary search in a non-trivial way. It's the "weighted job scheduling" problem with an attendance budget k. Candidates who recognize this as DP on sorted intervals (similar to weighted interval scheduling) and add the k-events dimension demonstrate strong algorithm design skills.

Algorithmic pattern used

DP with binary search: Sort events by end day. Define dp[i][j] = maximum value from the first i events, attending at most j of them. For event i:

• Skip it: dp[i][j] = dp[i-1][j]
• Attend it: find the latest event l that ends before event i starts (using binary search). dp[i][j] = dp[l][j-1] + value[i].

Transition: dp[i][j] = max(dp[i-1][j], dp[l][j-1] + value[i]).

The binary search finds l in O(log n). Total complexity: O(nklog n).

Example explanation

Events (start, end, value): [[1,2,4],[3,4,3],[2,3,1]], k=2.

• Sorted by end: [[1,2,4],[2,3,1],[3,4,3]].
• dp[0][j] = 0 for all j.
• Event 0 (end=2, val=4): No previous non-overlapping event. dp[1][1]=4, dp[1][2]=4.
• Event 1 (end=3, start=2, val=1): Events ending before day 2: event 0 ends at 2, which overlaps (need end < start=2, so need end ≤ 1). No valid previous. dp[2][1]=max(4,0+1)=4, dp[2][2]=max(4,0+1)=4.
• Event 2 (end=4, start=3, val=3): Events ending before day 3: event 0 (end=2) and event 1 (end=3, end<3 is false). l = event 0. dp[3][1]=max(4,0+3)=4, dp[3][2]=max(4,dp[1][1]+3)=max(4,4+3)=7.
• Answer = dp[3][2] = 7.

Attend events 0 (value 4) and 2 (value 3) on days 1 and 3 respectively. Total = 7.

Common mistakes candidates make

• Confusing "end < start" with "end ≤ start": Two events can be attended on the same day only if one ends before the other starts. "End < start of next event" means no-overlap in the 1-day sense.
• Not using binary search for the previous event: O(n) scan per event makes this O(n²k), likely too slow.
• Incorrect DP dimension: The j dimension must range from 0 to k; initializing it incorrectly leads to wrong answers.

Interview preparation tip

For the Array Sorting Binary Search Dynamic Programming interview pattern, weighted job scheduling (this problem) is a must-know template. Memorize: sort by end time, binary search for last non-overlapping job, DP with the choice of "skip or take." The k-events extension simply adds a second DP dimension. Practice the basic weighted interval scheduling first, then add the budget dimension.