LeetCode 1751 - Maximum Number of Events That Can Be Attended II

You are given a list of events, where each event is represented as: - startDay - endDay - value If you attend an event, you must attend the entire interval from startDay to endDay, inclusive.

leetcodehardarraybinary-searchdynamic-programmingsorting

LeetCode Problem 1751

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Sorting

Solution

Problem Understanding

You are given a list of events, where each event is represented as:

  • startDay
  • endDay
  • value

If you attend an event, you must attend the entire interval from startDay to endDay, inclusive. Because the interval is inclusive, two events conflict if one starts on the same day another ends.

You may attend at most k events, and the goal is to maximize the total collected value.

The challenge comes from combining two constraints at the same time:

  1. Events cannot overlap.
  2. You may select at most k events.

This immediately suggests that the problem is not just interval scheduling. We are not maximizing the number of events, we are maximizing weighted profit under a limit on how many intervals may be selected.

The input size is large enough that brute force is impossible:

  • events.length can be up to 10^5
  • k * events.length <= 10^6

That second constraint is important. It strongly hints that an O(n * k) dynamic programming solution is expected.

Another important observation is that event days can be as large as 10^9. This means we cannot build a DP based on actual calendar days. We must work directly with the events themselves.

A subtle but extremely important rule is that the end day is inclusive. If one event ends on day 5, another event starting on day 5 is considered overlapping. The next compatible event must start strictly after the current event's end day.

Several edge cases can easily cause bugs:

  • Events that touch at endpoints, such as [1,2] and [2,3]
  • Situations where taking fewer than k events is optimal
  • Multiple overlapping events with very different values
  • k = 1, which reduces the problem to selecting the single best event
  • All events non-overlapping, where the answer becomes selecting the top k profitable events in chronological compatibility order

Approaches

Brute Force

The most direct approach is to try every subset of events up to size k.

For each subset, we would:

  1. Check whether the events overlap.
  2. Compute the total value.
  3. Keep the maximum valid total.

This works because it exhaustively explores every possible combination, guaranteeing that the best answer will eventually be found.

Unfortunately, the number of subsets is exponential. With n events, there are 2^n possible subsets. Even if we prune selections larger than k, the complexity is still enormous.

This becomes completely infeasible once n reaches even a few dozen, while the actual constraints allow up to 10^5 events.

Key Insight

This problem is a classic combination of:

  • Weighted interval scheduling
  • Dynamic programming
  • Binary search

The critical observation is that after sorting events by start time, when we decide whether to take an event, we only need to know:

  • Which event index we are currently considering
  • How many events we may still take

If we choose the current event, we must jump to the next non-overlapping event. Since the events are sorted, we can locate that next compatible event using binary search.

This transforms the exponential search into a dynamic programming problem.

Define:

dp(i, remaining) = maximum value obtainable starting from event i with remaining selections left.

At every event, we have two choices:

  1. Skip the event
  2. Take the event and jump to the next compatible event

The recurrence becomes:

  • Skip:

dp(i + 1, remaining)

  • Take:

value[i] + dp(nextIndex, remaining - 1)

We compute the maximum of these two options.

Because there are only n * k states, and each transition uses binary search, the solution becomes efficient enough for the constraints.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries every subset of events
Optimal DP + Binary Search O(n * k * log n) O(n * k) Uses memoization and binary search for next compatible event

Algorithm Walkthrough

  1. Sort all events by their start day.

Sorting allows us to process events in chronological order and enables binary search for the next compatible event. 2. Extract all start days into a separate array.

This array lets us efficiently binary search for the first event whose start day is strictly greater than the current event's end day. 3. Define a memoized recursive function:

dfs(index, remaining)

This function returns the maximum value obtainable starting from index when we may still attend remaining events. 4. Handle base cases.

If:

  • index == n, there are no more events
  • remaining == 0, we cannot attend additional events

then the answer is 0. 5. Compute the "skip" option.

Ignore the current event and move to the next one:

dfs(index + 1, remaining)
  1. Compute the "take" option.

If we attend the current event:

  • Add its value
  • Find the next non-overlapping event using binary search
  • Reduce remaining selections by one
value + dfs(nextIndex, remaining - 1)
  1. Store and return the maximum of the two choices.

Memoization ensures each state is computed only once. 8. Start the recursion from:

dfs(0, k)

Why it works

At every event, the algorithm considers the only two valid possibilities: either attend the event or skip it. Because events are processed in sorted order, binary search correctly identifies the next compatible event. Memoization guarantees that every subproblem is solved once, and every valid combination of non-overlapping events is considered through the recursive decisions. Therefore, the algorithm always finds the optimal total value.

Python Solution

from typing import List
from functools import lru_cache
from bisect import bisect_right

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort()

        start_days = [event[0] for event in events]
        n = len(events)

        @lru_cache(None)
        def dfs(index: int, remaining: int) -> int:
            if index == n or remaining == 0:
                return 0

            skip = dfs(index + 1, remaining)

            start, end, value = events[index]

            next_index = bisect_right(start_days, end)

            take = value + dfs(next_index, remaining - 1)

            return max(skip, take)

        return dfs(0, k)

The implementation begins by sorting events according to their start day. This guarantees that all future compatible events appear after the current event.

The start_days array exists purely to support binary search. Since we need the first event whose start day is strictly greater than the current event's end day, bisect_right is the perfect tool.

The recursive function dfs(index, remaining) represents the best answer achievable starting from a particular event index with a limited number of selections remaining.

The memoization cache is essential. Without it, the recursion would repeatedly solve identical subproblems and become exponential.

Inside the recursion, two decisions are evaluated:

  • Skip the current event
  • Take the current event and jump directly to the next compatible event

The algorithm returns whichever choice produces the larger total value.

Go Solution

package main

import (
	"sort"
)

func maxValue(events [][]int, k int) int {
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})

	n := len(events)

	startDays := make([]int, n)
	for i := 0; i < n; i++ {
		startDays[i] = events[i][0]
	}

	memo := make([][]int, n)
	for i := 0; i < n; i++ {
		memo[i] = make([]int, k+1)
		for j := 0; j <= k; j++ {
			memo[i][j] = -1
		}
	}

	var dfs func(int, int) int

	dfs = func(index int, remaining int) int {
		if index == n || remaining == 0 {
			return 0
		}

		if memo[index][remaining] != -1 {
			return memo[index][remaining]
		}

		skip := dfs(index+1, remaining)

		end := events[index][1]
		value := events[index][2]

		nextIndex := sort.Search(n, func(i int) bool {
			return startDays[i] > end
		})

		take := value + dfs(nextIndex, remaining-1)

		if take > skip {
			memo[index][remaining] = take
		} else {
			memo[index][remaining] = skip
		}

		return memo[index][remaining]
	}

	return dfs(0, k)
}

The Go implementation follows the same algorithmic structure as the Python version.

Instead of Python's lru_cache, Go uses a manually allocated 2D memoization table initialized with -1.

Binary search is implemented with sort.Search, which finds the first index satisfying the condition startDays[i] > end.

Go slices are naturally dynamic, so no special handling for empty arrays is required. Integer overflow is also not a concern here because the maximum possible answer fits comfortably inside Go's int on LeetCode platforms.

Worked Examples

Example 1

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

After sorting:

Index Event
0 [1,2,4]
1 [2,3,1]
2 [3,4,3]

Start days:

[1, 2, 3]

Now evaluate recursively.

State: dfs(0, 2)

Current event:

[1,2,4]

Binary search for first start day > 2:

nextIndex = 2

Choices:

Choice Value
Skip dfs(1,2)
Take 4 + dfs(2,1)

State: dfs(2,1)

Current event:

[3,4,3]

Next compatible index:

3

Choices:

Choice Value
Skip 0
Take 3 + 0 = 3

Result:

dfs(2,1) = 3

So:

take = 4 + 3 = 7

The skip branch cannot exceed this value, so the final answer becomes:

7

Example 2

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

Sorted events:

Index Event
0 [1,2,4]
1 [2,3,10]
2 [3,4,3]

At event [2,3,10], the next compatible event must start after day 3.

Event [3,4,3] starts exactly on day 3, so it overlaps.

Therefore, taking value 10 prevents selecting any other event.

The algorithm correctly identifies that 10 is better than combinations like 4 + 3 = 7.

Final answer:

10

Example 3

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

All events are non-overlapping.

The optimal choice is the three highest-value events:

2 + 3 + 4 = 9

The DP naturally explores all possibilities and discovers this maximum.

Complexity Analysis

Measure Complexity Explanation
Time O(n * k * log n) There are n * k DP states, each performing one binary search
Space O(n * k) Memoization table stores one result per state

The sorting step costs O(n log n), but the dynamic programming dominates the runtime. Since each state performs only constant work plus a binary search, the total complexity becomes O(n * k * log n).

The memoization table stores all computed states, producing O(n * k) memory usage.

Test Cases

sol = Solution()

# Example 1
assert sol.maxValue([[1,2,4],[3,4,3],[2,3,1]], 2) == 7

# Example 2
assert sol.maxValue([[1,2,4],[3,4,3],[2,3,10]], 2) == 10

# Example 3
assert sol.maxValue([[1,1,1],[2,2,2],[3,3,3],[4,4,4]], 3) == 9

# Single event
assert sol.maxValue([[1,5,100]], 1) == 100

# k larger than number of events
assert sol.maxValue([[1,1,2],[2,2,3]], 10) == 5

# Overlapping events where best single event wins
assert sol.maxValue([[1,10,5],[2,3,100],[4,5,100]], 1) == 100

# Inclusive overlap check
assert sol.maxValue([[1,2,5],[2,3,6]], 2) == 6

# Non-overlapping chain
assert sol.maxValue([[1,1,5],[2,2,6],[3,3,7]], 2) == 13

# All events overlap
assert sol.maxValue([[1,5,1],[1,5,2],[1,5,3]], 2) == 3

# Larger mixed case
assert sol.maxValue(
    [[1,2,4],[3,4,3],[2,3,10],[5,6,8],[7,8,9]],
    3
) == 27

Test Summary

Test Why
Example 1 Standard overlapping and non-overlapping combination
Example 2 Best answer uses fewer than k events
Example 3 All events compatible
Single event Smallest non-trivial input
k larger than events Ensures algorithm handles oversized k
Best single event Verifies optimal value selection
Inclusive overlap Confirms strict non-overlap condition
Non-overlapping chain Tests selecting top compatible values
All events overlap Ensures only one event may be selected
Larger mixed case Stress test with multiple transitions

Edge Cases

One important edge case is events that touch at endpoints. For example, [1,2] and [2,3] overlap because the end day is inclusive. Many implementations incorrectly allow these events together. This solution avoids that mistake by using bisect_right(start_days, end), which finds the first event whose start day is strictly greater than the current end day.

Another important case is when taking fewer than k events produces the optimal answer. Some incorrect solutions try to force exactly k selections. The DP here does not require selecting exactly k events. It simply explores all valid possibilities up to k, allowing the algorithm to correctly return answers like 10 in Example 2.

A third tricky case occurs when all events overlap. In such situations, the algorithm must correctly identify the single highest-value event. Since every state considers both skipping and taking the current event, the recursion naturally compares all overlapping alternatives and keeps the best one.

A final subtle edge case involves very large day values, up to 10^9. Any solution based on iterating over days would fail either in runtime or memory usage. This implementation never depends on actual calendar ranges. It works entirely with sorted event indices and binary search, making it efficient regardless of how large the day numbers become.