HardArrayBinary SearchDynamic ProgrammingSortingUpdated Sep 2026

1751. Maximum Number of Events That Can Be Attended II

Asked at Snowflake

Difficulty

Hard

Time

O(n log n + n * k)

Space

O(n * k)

Pattern

Array

Companies

1

Problem

You get a list of events. Each event is [startDay, endDay, value]: it runs from startDay to endDay (both days included) and pays value if you attend it.

You may attend at most k events. You must attend an event for its whole duration, and you can only be at one event at a time. Because the end day counts, two events conflict if one ends on the same day the other starts — so an event ending on day d blocks any event starting on day d.

Return the maximum total value you can collect. You do not have to use all k slots; attending fewer events is fine if that pays more.

Pick non-overlapping events, at most k

events[1,2] v4[3,4] v3[2,3] v1012With k = 2, events 0 and 1 fit together: 4 + 3 = 7day lineevent 0event 11234Event 0 covers days 1-2, event 1 covers days 3-4, sothey never touch
Each bar is one event on the day line. Touching bars (end day = next start day) still conflict.

Constraints

  • ●1 <= k <= events.length
  • ●1 <= k * events.length <= 10^6
  • ●1 <= startDay_i <= endDay_i <= 10^9
  • ●1 <= value_i <= 10^6

Examples

Example 1
Inputevents = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output7
WhyTake event 0 (days 1-2, value 4) and event 1 (days 3-4, value 3). Day 2 ends before day 3 starts, so they do not conflict. Total = 7, which beats any other pair.
Example 2
Inputevents = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output10
WhyEvent 2 (days 2-3, value 10) overlaps both other events, so taking it means taking nothing else. 10 is still better than 4 + 3 = 7, so the answer is 10.
Example 3
Inputevents = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output9
WhyNo two events overlap, but you may only attend 3 of the 4. The three best values are 2, 3 and 4, giving 9.

Asked At

1 companies
CompanyDifficulty
SnowflakeHardView all Snowflake questions →

How to Think About It

1

Without the k limit this is Maximum Profit in Job Scheduling. The limit adds a second DP dimension.

2

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).

3

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]).

4

Fill the table from i = n - 1 down to 0 so that dp[i+1] and dp[nxt[i]] are ready.

5

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).

DP over sorted events

dp[i][j]j=0j=1j=2i=3i=2i=1i=0000000000000Rows are events from last to first, columns are how manyevents you may still takesort by start daynxt[i] = first start > end_iskip: dp[i+1][j]take: value_i + dp[nxt[i]][j-1]answer = dp[0][k]Fill the table bottom-up so both dp[i+1] and dp[nxt[i]]are already knowndp[i][j] = max(dp[i+1][j], value_i + dp[nxt[i]][j-1])
Sort by start day, then decide for each event: skip it, or take it and jump to the first event that starts after it ends.
ComplexityTime O(n log n + n * k)Space O(n * k)Sorting and the binary searches cost O(n log n); the DP table has (n+1) x (k+1) cells and each is filled in O(1).

What Trips People Up in Real Interviews

1

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.

2

Ignoring k and solving the unlimited version.

3

Memoized recursion in Python over 10^6 states can hit recursion limits — prefer the bottom-up table.

4

Greedy by value or by end time. Neither handles the value/count trade-off.

Solution Code

O(n log n + n * k) time
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]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n log n + n * k) time and O(n * k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.