#1751

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Number of Events That Can Be Attended II

Determine the maximum sum of event values you can collect by attending at most k non-overlapping events using DP.

array binary search dynamic programming sorting

Problem Statement

You are given a list of events where each event is represented as [startDay, endDay, value]. You may attend at most k events. Each event requires full attendance from start to end, and no two attended events can overlap.

Return the maximum total value achievable by attending up to k events. The end day of an event is inclusive, so you cannot attend two events that share any day. Optimize for selecting events that maximize value without conflicts.

Examples

Example 1

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2

Output: 7

Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2

Output: 10

Choose event 2 for a total value of 10. Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3

Output: 9

Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints

1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106

Solution Approach

Sort Events by Start Day

Begin by sorting all events in ascending order of their start day. This ensures that when processing events in sequence, you can use binary search to efficiently find the next event that does not overlap with the current one.

Dynamic Programming with State Transitions

Use a DP table dp[i][j] where i is the index of the event and j is the number of events attended. For each event, consider two options: skip it (dp[i+1][j] = max(dp[i+1][j], dp[i][j])) or attend it and add its value plus the optimal solution of remaining events using binary search to find the next non-overlapping event.

Binary Search for Next Compatible Event

To efficiently determine the next event that can be attended after choosing an event, perform binary search on the sorted list using the end day of the current event. This avoids checking all future events and keeps the DP transitions within manageable complexity.

Complexity Analysis

Metric	Value
Time	O(n \cdot (n\cdot k + \log n))
Space	O(n \cdot k)

Time complexity is O(n * (k + log n)) because for each event and each possible attended count up to k, binary search is performed to find the next compatible event. Space complexity is O(n * k) to store the DP table for state transitions.

What Interviewers Usually Probe

They may ask about handling overlapping events efficiently using binary search after sorting.
Expect questions on optimizing DP transitions for large n * k to avoid timeouts.
Clarify why attending fewer than k events may be optimal if higher-value events overlap.

Common Pitfalls or Variants

Common pitfalls

Forgetting that end days are inclusive, which causes overlaps if not handled carefully.
Not sorting events before binary search, leading to incorrect next-event selection.
Assuming you must attend exactly k events instead of at most k, which can reduce total value.

Follow-up variants

Modify to return the actual sequence of events that maximizes value, not just the sum.
Change k to be dynamic per event, allowing variable attendance limits.
Introduce additional constraints such as minimum rest days between events.

FAQ

What pattern is used in Maximum Number of Events That Can Be Attended II?

This problem follows the state transition dynamic programming pattern, where each decision depends on previously attended events and remaining capacity.

Do I have to attend exactly k events?

No, you can attend up to k events. Attending fewer events may yield a higher total value if overlapping events have higher values.

Why is sorting events by start day necessary?

Sorting allows binary search to efficiently locate the next non-overlapping event, reducing the time complexity of DP transitions.

What is the main reason this DP approach avoids TLE?

Using binary search to find compatible events avoids checking all future events, keeping the DP transitions within O(n * k * log n).

Can this method handle large ranges for startDay and endDay?

Yes, since the algorithm does not iterate over day ranges directly but relies on event indices and binary search, it scales to large day values.

terminal

Solution

Solution 1: Memoization + Binary Search

First, we sort the events by their start time in ascending order. Then, we define a function $\text{dfs}(i, k)$, which represents the maximum total value achievable by attending at most $k$ events starting from the $i$-th event. The answer is $\text{dfs}(0, k)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if i >= len(events):
                return 0
            _, ed, val = events[i]
            ans = dfs(i + 1, k)
            if k:
                j = bisect_right(events, ed, lo=i + 1, key=lambda x: x[0])
                ans = max(ans, dfs(j, k - 1) + val)
            return ans

        events.sort()
        return dfs(0, k)

Solution 2: Dynamic Programming + Binary Search

We can convert the memoization approach in Solution 1 to dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if i >= len(events):
                return 0
            _, ed, val = events[i]
            ans = dfs(i + 1, k)
            if k:
                j = bisect_right(events, ed, lo=i + 1, key=lambda x: x[0])
                ans = max(ans, dfs(j, k - 1) + val)
            return ans

        events.sort()
        return dfs(0, k)

Continue Practicing

#2008 maximum earnings from taxi #2054 two best non overlapping events #1235 maximum profit in job scheduling