Problem Statement

You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this event, you will receive a value of valuei. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Test Cases

Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: 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
Explanation: 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
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Intuition

The core idea is to evaluate, for each event, two possible decisions:

• Skip the event: simply move to the next index.

• Attend the event: add its value, and move to the next available event that starts after the current event’s end day.

Since we're constrained by a limit of k events, and decisions depend on both current index and remaining count k, this naturally leads to overlapping subproblems — perfect for memoization.

To efficiently find the next non-overlapping event, we use binary search, as the events are sorted by start time.

if we skip, then 0 + f(event, index + 1, k)
if we do not skip, then val + f(event, index + 1, k - 1)

Approach

1. Sort the events by their startDay to enable binary search.
2. Define a recursive function findMaxValue(events, k, index, dp):
   • Base case: if k == 0 or index is out of bounds, return 0.
   • Memoization: return cached value if already computed.
   • Recursive logic:
     • Skip the current event → findMaxValue(events, k, index + 1)
     • Attend the event → add its value + recurse from the next non-overlapping event.
3. Use binary search to find the next non-overlapping event whose startDay > current.endDay.
4. Store results in dp[index][k] to avoid recomputation.

Complexity

Time Complexity

• O(n log n + n * k)
  • Sorting: O(n log n)
  • Each state dp[i][k] is computed once.
  • Binary search per state is O(log n) but efficient in practice.

Space Complexity

• O(n * k) for the memoization table.
• Recursion stack space: O(k) in the worst case.

Code

class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]); 
        int n = events.length;
        int [][] dp = new int [n][k + 1];
        for (int [] d : dp) {
            Arrays.fill(d, -1);
        }
        return findMaxValue(events, k, 0, dp);
    }

    private int findMaxValue(int [][] events, int k, int index, int [][] dp) {
        if (k < 1) {
            return 0;
        }
        if (index >= events.length) {
            return 0;
        }
        if (dp[index][k] != -1) {
            return dp[index][k];
        }
        int skipEvent = findMaxValue(events, k, index + 1, dp);
        int nextIndex = findNextStart(events, index + 1, events[index][1]);
        int attendEvent = events[index][2];
        if (nextIndex != -1) {
            attendEvent += findMaxValue(events, k - 1, nextIndex, dp);
        }
        return dp[index][k] = Math.max(skipEvent, attendEvent);
    }

    private int findNextStart(int [][] events, int left, int key) {
        int right = events.length - 1;
        int answer = -1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (events[middle][0] > key) {
                answer = middle;
                right = middle - 1;
            }
            else {
                left = middle + 1;
            }
        }
        return answer;
    }
}