Maximum Number of Events That Can Be Attended II: DP with Binary Search

You are given an array of events where events[i] = [startDay, endDay, value] and an integer k. You can attend at most k events. You cannot attend two events where one starts on the same day another ends. Return the maximum sum of values of the events you attend.

This is LeetCode 1751: Maximum Number of Events That Can Be Attended II, and it is one of the best problems for learning the "weighted interval scheduling" pattern using DP and binary search together.

Why this problem matters

Interval scheduling shows up constantly in real systems: scheduling meetings, allocating resources, planning jobs on machines. The basic version asks you to maximize the count of non-overlapping intervals. This problem cranks it up by assigning values to each interval and limiting you to at most k picks. That combination of "select at most k non-overlapping intervals to maximize total value" is the weighted interval scheduling problem, and the DP + binary search approach you learn here transfers directly to job scheduling, booking systems, and any scenario where you pick from overlapping options with different payoffs.

The key insight

Sort events by end day. For each event, you have two choices: skip it or attend it. If you skip, the answer stays the same as the previous event. If you attend, you need to find the latest event that ends strictly before this event starts, so the two do not overlap. That lookup is a binary search on the sorted end days, which makes it O(log n) per event instead of a linear scan.

The DP recurrence is dp[i][j] = max(dp[i-1][j], dp[p][j-1] + value[i]) where p is the index of the latest non-overlapping event found by binary search.

1. Sort events by end day.
2. Build a 2D DP table where dp[i][j] = maximum value using the first i events and attending at most j.
3. For each event i, binary search for the latest event p whose end day is strictly less than event i's start day.
4. For each j from 1 to k: either skip event i (take dp[i-1][j]) or attend it (take dp[p][j-1] + value[i]). Pick the larger.
5. Return dp[n][k].

The solution

from bisect import bisect_right

def max_value(events: list[list[int]], k: int) -> int:
    events.sort(key=lambda e: e[1])
    n = len(events)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    ends = [e[1] for e in events]

    for i in range(1, n + 1):
        start_i = events[i - 1][0]
        val_i = events[i - 1][2]
        p = bisect_right(ends, start_i - 1, 0, i - 1)

        for j in range(1, k + 1):
            dp[i][j] = max(dp[i - 1][j], dp[p][j - 1] + val_i)

    return dp[n][k]

Let's walk through what each piece does.

The events are sorted by end day so that binary search works correctly. When processing event i, all earlier events in the sorted order have smaller or equal end days, which means binary search can efficiently find the latest compatible one.

The ends array holds every event's end day. For event i, we compute bisect_right(ends, start_i - 1, 0, i - 1) to find the rightmost event that ends at or before start_i - 1. Since an event ending on day d conflicts with an event starting on day d, we need the previous event to end strictly before our start day.

The inner loop iterates over j from 1 to k. For each value of j, we pick the better of two options: skipping event i (inheriting dp[i-1][j]) or attending it (adding its value to the best we can do with j-1 events among those that do not overlap).

Visual walkthrough

Let's trace through the example with events [[1,3,4],[2,4,7],[3,5,2],[4,6,3],[5,7,5]] and k = 2. After sorting by end day, the order stays the same. Watch how binary search finds the latest compatible event at each step.

Notice how the binary search at step 5 finds event E2 (ending on day 4) as the latest event compatible with E5 (starting on day 5). Pairing E2's value of 7 with E5's value of 5 gives us 12, which beats every other combination of two events.

Complexity analysis

Time is O(n * k * log n). Sorting takes O(n log n). For each of the n events, we do one binary search (O(log n)) and iterate over k values of j. The total is O(n log n + n * k * log n), which simplifies to O(n * k * log n) since k is at least 1.

Space is O(n * k) for the DP table. Each of the n + 1 rows has k + 1 columns. The ends array adds O(n), which does not change the overall bound.

The building blocks

1. Binary search for the latest non-overlapping interval

The pattern of using binary search to find the latest interval that does not conflict with the current one:

from bisect import bisect_right

ends = [e[1] for e in sorted_events]
p = bisect_right(ends, start_i - 1, 0, i - 1)

When intervals are sorted by end day, you can binary search for the insertion point of start_i - 1 in the ends array. The result is the count of events whose end day is <= start_i - 1, which also happens to be the index of the first event that ends after that threshold. So p is the number of compatible events, and dp[p] captures the best solution among them. You will reuse this pattern in any weighted interval scheduling variant.

2. 2D DP with a "take or skip" recurrence

The pattern of building a DP table where one dimension tracks items and the other tracks a budget:

dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, k + 1):
        dp[i][j] = max(dp[i - 1][j], dp[p][j - 1] + val_i)

This is the same structure as the 0/1 knapsack: for each item, you either skip it (carry forward the previous row) or take it (add its value and decrement the budget). The twist here is that "taking" does not look at dp[i-1] but at dp[p], where p comes from binary search. You see this 2D take-or-skip recurrence in knapsack, subset selection, and scheduling problems whenever you have a limited budget.

Edge cases

Before submitting, think through these scenarios:

• k = 1: you just need the single event with the highest value. The DP still works, but a simpler scan would suffice.
• All events overlap: every event conflicts with every other. You can only pick the single most valuable one regardless of k.
• No overlaps at all: every event is compatible with every other. Pick the top k by value. The DP handles this because binary search always finds the immediately preceding event.
• k >= n: you can attend everything. The answer is the sum of all values, since the constraint never binds.
• Single event: return its value. The DP table is trivially filled.
• Events with equal end days: sorting is stable, and binary search correctly finds the boundary. Two events ending on the same day may or may not conflict depending on their start days.

From understanding to recall

You have seen how DP plus binary search solves weighted interval scheduling: sort by end day, binary search for the latest non-overlapping event, and fill a 2D table with a take-or-skip recurrence. The logic is clean once you understand it.

But the details matter under pressure. Do you search for start_i or start_i - 1? Do you use bisect_left or bisect_right? Does p point to the last compatible event or the first incompatible one? These are exactly the kind of off-by-one mistakes that cost people in interviews, and they only go away with deliberate practice.

Spaced repetition closes that gap. You practice writing the binary search for the latest non-overlapping interval, the 2D DP recurrence, and the sorting setup from scratch at increasing intervals. After a few rounds, the pattern becomes automatic. When you see "maximize value from at most k non-overlapping intervals," you do not hesitate. You sort, search, and fill the table.

Related posts

• Jump Game II - Greedy interval jumping
• Insert Interval - Interval manipulation fundamentals
• Merge Intervals - The foundational interval problem

CodeBricks breaks Maximum Number of Events That Can Be Attended II into its binary search lookup and 2D DP recurrence building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a weighted interval scheduling problem shows up in your interview, you do not think about it. You just write it.