# Maximum Number of Events That Can Be Attended II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-events-that-can-be-attended-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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._

**Example 1:**

![](https://assets.glich.co/dsa/maximum-number-of-events-that-can-be-attended-ii/image0.png)

**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:**

![](https://assets.glich.co/dsa/maximum-number-of-events-that-can-be-attended-ii/image1.png)

**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:**

**![](https://assets.glich.co/dsa/maximum-number-of-events-that-can-be-attended-ii/image2.png)**

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

**Constraints:**

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

# Approaches
## Brute-Force Recursion
This fundamental approach uses recursion to explore every possible valid combination of events. For each event, we decide whether to attend it or skip it. If we choose to attend an event, we add its value and then recursively find the best combination for the remaining non-overlapping events. If we skip it, we move to the next event. This method exhaustively checks all possibilities to find the maximum value.
**Time:** O(2^n), where n is the number of events. In the worst case, for each event, we branch into two possibilities, leading to an exponential number of calls. · **Space:** O(n), where n is the number of events. This is for the recursion call stack depth in the worst case.
**Pros:** Simple to conceptualize and implement.; Correctly models the decision-making process of the problem.
**Cons:** Extremely inefficient due to exponential time complexity.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input because it recomputes the same subproblems multiple times.
### Explanation
The brute-force recursive solution forms the basis for more optimized dynamic programming approaches. It models the problem as a series of decisions. We first sort the events by their start day to handle the non-overlapping constraint systematically.

The core of this method is a recursive function `solve(index, k_left)`. This function calculates the maximum value obtainable from the subarray of events `events[index:]` given we can still attend `k_left` events.

For each event `events[index]`, the function explores two paths:
1.  **Skip**: We ignore the current event and the problem reduces to finding the maximum value from the remaining events `events[index+1:]` with the same `k_left` allowance. This is `solve(index + 1, k_left)`.
2.  **Attend**: We take the value of `events[index]` and then look for the next compatible event. A compatible event `j` must start after `events[index]` has finished, i.e., `events[j][0] > events[index][1]`. We find the first such event `j` and recursively call `solve(j, k_left - 1)`. The total value for this path is `events[index][2] + solve(j, k_left - 1)`.

The function returns the maximum of these two outcomes. The final answer is the result of the initial call `solve(0, k)`.
### Algorithm
1. Sort the `events` array based on their start times.
2. Define a recursive function, let's say `solve(index, count)`, which will return the maximum value we can obtain from the events starting from `index` onwards, given that we can still attend `count` more events.
3. **Base Cases** for the recursion:
    - If `count` is 0 (we cannot attend any more events) or `index` is out of bounds (no more events to consider), return 0.
4. **Recursive Step**: For the event at the current `index`, we have two choices:
    - **Skip the event**: We don't attend `events[index]`. The maximum value we can get is by moving to the next event: `solve(index + 1, count)`.
    - **Attend the event**: We attend `events[index]` and add its value. Then, we must find the next event that does not overlap. Since the events are sorted by start time, we can find the first event `j` such that `events[j][0] > events[index][1]`. The total value for this choice is `events[index][2] + solve(j, count - 1)`.
5. The function `solve(index, count)` returns the maximum of the values from these two choices.
6. The initial call to start the process is `solve(0, k)`.

## Top-Down Dynamic Programming with Memoization
This approach significantly optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. The key observation is that the recursive solution solves the same subproblems repeatedly. By storing the result of each subproblem `(index, k_left)` in a 2D array, we can avoid re-computation and retrieve the stored result in constant time. This turns the exponential complexity into a polynomial one.
**Time:** O(n * k * log n). Sorting takes O(n log n). There are O(n * k) states, and each state computation involves a binary search which takes O(log n) time. · **Space:** O(n * k) for the memoization table, plus O(n) for the recursion stack. The total space is dominated by the table.
**Pros:** Drastically more efficient than brute-force.; Guaranteed to find the optimal solution.; The logic is a direct extension of the recursive solution, making it relatively easy to understand.
**Cons:** The space complexity of O(n * k) can be large, potentially leading to memory issues if both n and k are large (though the problem constraints `n * k <= 10^6` make it manageable).; Recursive solutions might lead to stack overflow for very deep recursion paths, although this is unlikely with the given constraints.
### Explanation
To implement this, we first sort the events by their start times. We then define a recursive helper function, say `solve(index, count)`, which computes the maximum value from events `events[index:]` with `count` available slots. A 2D array `memo[n][k+1]` is used to store the results.

Inside `solve(index, count)`:
- We first check the base cases: if `count` is zero or `index` is out of bounds, we return 0.
- Then, we check our `memo` table. If `memo[index][count]` has been computed, we return the stored value immediately.
- Otherwise, we compute the result by considering the two choices for `events[index]`:
    1. **Skip**: `solve(index + 1, count)`.
    2. **Attend**: `events[index][2] + solve(nextIndex, count - 1)`. To find `nextIndex` (the first event starting after `events[index]` ends), we perform a binary search on the sorted `events` array. This is efficient, taking `O(log n)` time.
- We take the maximum of the two choices, store it in `memo[index][count]`, and return it.
The initial call is `solve(0, k)`.
```java
class Solution {
    int[][] memo;
    int[][] events;
    int n;

    public int maxValue(int[][] events, int k) {
        this.n = events.length;
        this.events = events;
        Arrays.sort(this.events, (a, b) -> a[0] - b[0]);
        this.memo = new int[n][k + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(0, k);
    }

    private int solve(int index, int count) {
        if (count == 0 || index == n) {
            return 0;
        }
        if (memo[index][count] != -1) {
            return memo[index][count];
        }

        // Option 1: Skip the current event
        int skip = solve(index + 1, count);

        // Option 2: Attend the current event
        // Find the next event that can be attended using binary search
        int nextIndex = binarySearch(index + 1, events[index][1]);
        int attend = events[index][2] + solve(nextIndex, count - 1);

        return memo[index][count] = Math.max(attend, skip);
    }

    // Returns the index of the first event in events[fromIndex...] with start time > target
    private int binarySearch(int fromIndex, int target) {
        int left = fromIndex, right = n - 1, ans = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (events[mid][0] > target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
1. Sort the `events` array based on their start times.
2. Create a 2D memoization table, `memo[n][k+1]`, initialized with a sentinel value (e.g., -1) to store the results of subproblems.
3. Define a recursive function `solve(index, count)`.
4. **Base Cases**: If `count == 0` or `index >= n`, return 0.
5. **Memoization Check**: If `memo[index][count]` is not -1, it means the result for this state `(index, count)` has already been computed, so return `memo[index][count]`.
6. **Recursive Step**: If the result is not in the memo table:
    - Calculate the value if we **skip** `events[index]`: `skip_value = solve(index + 1, count)`.
    - Calculate the value if we **attend** `events[index]`: Find the index of the next non-overlapping event, `nextIndex`, using binary search. The value is `attend_value = events[index][2] + solve(nextIndex, count - 1)`.
7. Store the maximum of `skip_value` and `attend_value` in `memo[index][count]` and return it.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach, primarily in terms of memory usage. It's a bottom-up, iterative dynamic programming solution. By observing that the calculation for attending `j` events only depends on the results for `j-1` events, we can optimize the space complexity from O(n * k) to O(n). We use two 1D arrays to store the DP states for the current and previous number of events, effectively reducing the memory footprint.
**Time:** O(n * k * log n). The complexity is dominated by the nested loops (k * n iterations) and the binary search (log n) inside the inner loop. · **Space:** O(n). We use two arrays of size n+1 to store the DP states, which is a significant improvement over O(n * k).
**Pros:** Optimal space complexity of O(n).; Avoids recursion, preventing potential stack overflow issues.; Efficient enough to pass within the given constraints.
**Cons:** The time complexity remains O(n * k * log n), which might be slow if the constraints were tighter.; The logic can be slightly less intuitive to formulate compared to the top-down recursive approach.
### Explanation
The core idea is to build the solution iteratively. We first sort events by start time. The DP state `dp[i]` will represent the maximum value obtainable from events `events[i:]`.

We use an outer loop for the number of events allowed, `j`, from 1 to `k`. For each `j`, we compute the maximum values using an inner loop that iterates through the events `i` from `n-1` down to `0`.

We maintain two arrays: `prev_dp` stores the results for `j-1` events, and `curr_dp` is used to compute the results for `j` events.

The state transition for `curr_dp[i]` is:
`curr_dp[i] = max(curr_dp[i+1], events[i][2] + prev_dp[nextIndex])`
- `curr_dp[i+1]` represents the choice of skipping `events[i]`. It's the max value from `events[i+1:]` using `j` events.
- `events[i][2] + prev_dp[nextIndex]` represents attending `events[i]`. `prev_dp[nextIndex]` gives the max value from compatible future events using `j-1` events.

After computing `curr_dp` for all `i`, it becomes the `prev_dp` for the next `j`. The final answer is the value for `k` events considering from index 0.

```java
class Solution {
    public int maxValue(int[][] events, int k) {
        int n = events.length;
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        
        int[] dp = new int[n + 1];

        for (int j = 1; j <= k; j++) {
            int[] next_dp = new int[n + 1];
            for (int i = n - 1; i >= 0; i--) {
                // Option 1: Skip event i
                int skip = next_dp[i + 1];

                // Option 2: Attend event i
                int nextIndex = binarySearch(events, i + 1, events[i][1]);
                int attend = events[i][2] + dp[nextIndex];

                next_dp[i] = Math.max(skip, attend);
            }
            dp = next_dp;
        }
        return dp[0];
    }

    private int binarySearch(int[][] events, int fromIndex, int target) {
        int left = fromIndex, right = events.length - 1, ans = events.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (events[mid][0] > target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
1. Sort the `events` array by their start times.
2. Create two 1D arrays, `prev_dp` and `curr_dp`, of size `n+1`, initialized to 0. `prev_dp` will store results for `j-1` events, and `curr_dp` for `j` events.
3. Loop for the number of events to attend, `j`, from 1 to `k`.
4. Inside this loop, iterate through the events backwards, from `i = n-1` down to `0`.
5. For each `(i, j)`, calculate `curr_dp[i]`:
    - **Option 1 (Skip `events[i]`):** The value is `curr_dp[i+1]` (the max value from `events[i+1:]` with `j` events).
    - **Option 2 (Attend `events[i]`):** Find `nextIndex` using binary search. The value is `events[i][2] + prev_dp[nextIndex]` (value of current event plus max value from compatible events using `j-1` slots).
    - `curr_dp[i] = max(Option 1, Option 2)`.
6. After the inner loop (for `i`) finishes, `curr_dp` holds the optimal values for `j` events. Update `prev_dp` with the values of `curr_dp` for the next iteration of `j`.
7. The final answer is `prev_dp[0]` after the outer loop completes.

# Solutions
### Java

```java
class Solution {
private
  int[][] events;
private
  int[][] f;
private
  int n;
public
  int maxValue(int[][] events, int k) {
    Arrays.sort(events, (a, b)->a[0] - b[0]);
    this.events = events;
    n = events.length;
    f = new int[n][k + 1];
    return dfs(0, k);
  }
private
  int dfs(int i, int k) {
    if (i >= n || k <= 0) {
      return 0;
    }
    if (f[i][k] != 0) {
      return f[i][k];
    }
    int j = search(events, events[i][1], i + 1);
    int ans = Math.max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);
    return f[i][k] = ans;
  }
private
  int search(int[][] events, int x, int lo) {
    int l = lo, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (events[mid][0] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxValue(vector<vector<int>> &events, int k) {
    sort(events.begin(), events.end());
    int n = events.size();
    int f[n][k + 1];
    memset(f, 0, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int k) -> int {
      if (i >= n || k <= 0) {
        return 0;
      }
      if (f[i][k] > 0) {
        return f[i][k];
      }
      int ed = events[i][1], val = events[i][2];
      vector<int> t = {ed};
      int p = upper_bound(
                  events.begin() + i + 1, events.end(), t,
                  [](const auto &a, const auto &b) { return a[0] < b[0]; }) -
              events.begin();
      f[i][k] = max(dfs(i + 1, k), dfs(p, k - 1) + val);
      return f[i][k];
    };
    return dfs(0, k);
  }
};

```

### Python

```python
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)

```