Maximum Number of Events That Can Be Attended II

Hard

#1603Time: 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.

Patterns

Dynamic Programming

Algorithms

Binary Search Sorting

Data structures

Array

Prompt

You are given an array of events where events[i] = [startDay_i, endDay_i, value_i]. The i^th event starts at startDay_iand ends at endDay_i, and if you attend this event, you will receive a value of value_i. 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:

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.

Constraints:

1 <= k <= events.length
1 <= k * events.length <= 10⁶
1 <= startDay_i <= endDay_i <= 10⁹
1 <= value_i <= 10⁶

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

Sort the events array based on their start times.
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.
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.
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).
The function solve(index, count) returns the maximum of the values from these two choices.
The initial call to start the process is solve(0, k).

Walkthrough

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:

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

Complexity

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.

Trade-offs

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.

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.

Algorithm

Sort the events array based on their start times.
Create a 2D memoization table, memo[n][k+1], initialized with a sentinel value (e.g., -1) to store the results of subproblems.
Define a recursive function solve(index, count).
Base Cases: If count == 0 or index >= n, return 0.
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].
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).
Store the maximum of skip_value and attend_value in memo[index][count] and return it.

Walkthrough

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

1class Solution {2    int[][] memo;3    int[][] events;4    int n;5 6    public int maxValue(int[][] events, int k) {7        this.n = events.length;8        this.events = events;9        Arrays.sort(this.events, (a, b) -> a[0] - b[0]);10        this.memo = new int[n][k + 1];11        for (int[] row : memo) {12            Arrays.fill(row, -1);13        }14        return solve(0, k);15    }16 17    private int solve(int index, int count) {18        if (count == 0 || index == n) {19            return 0;20        }21        if (memo[index][count] != -1) {22            return memo[index][count];23        }24 25        // Option 1: Skip the current event26        int skip = solve(index + 1, count);27 28        // Option 2: Attend the current event29        // Find the next event that can be attended using binary search30        int nextIndex = binarySearch(index + 1, events[index][1]);31        int attend = events[index][2] + solve(nextIndex, count - 1);32 33        return memo[index][count] = Math.max(attend, skip);34    }35 36    // Returns the index of the first event in events[fromIndex...] with start time > target37    private int binarySearch(int fromIndex, int target) {38        int left = fromIndex, right = n - 1, ans = n;39        while (left <= right) {40            int mid = left + (right - left) / 2;41            if (events[mid][0] > target) {42                ans = mid;43                right = mid - 1;44            } else {45                left = mid + 1;46            }47        }48        return ans;49    }50}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Sort the events array by their start times.
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.
Loop for the number of events to attend, j, from 1 to k.
Inside this loop, iterate through the events backwards, from i = n-1 down to 0.
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).
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.
The final answer is prev_dp[0] after the outer loop completes.

Walkthrough

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.

1class Solution {2    public int maxValue(int[][] events, int k) {3        int n = events.length;4        Arrays.sort(events, (a, b) -> a[0] - b[0]);5        6        int[] dp = new int[n + 1];7 8        for (int j = 1; j <= k; j++) {9            int[] next_dp = new int[n + 1];10            for (int i = n - 1; i >= 0; i--) {11                // Option 1: Skip event i12                int skip = next_dp[i + 1];13 14                // Option 2: Attend event i15                int nextIndex = binarySearch(events, i + 1, events[i][1]);16                int attend = events[i][2] + dp[nextIndex];17 18                next_dp[i] = Math.max(skip, attend);19            }20            dp = next_dp;21        }22        return dp[0];23    }24 25    private int binarySearch(int[][] events, int fromIndex, int target) {26        int left = fromIndex, right = events.length - 1, ans = events.length;27        while (left <= right) {28            int mid = left + (right - left) / 2;29            if (events[mid][0] > target) {30                ans = mid;31                right = mid - 1;32            } else {33                left = mid + 1;34            }35        }36        return ans;37    }38}

Complexity

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

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int[][] events;4private5  int[][] f;6private7  int n;8public9  int maxValue(int[][] events, int k) {10    Arrays.sort(events, (a, b)->a[0] - b[0]);11    this.events = events;12    n = events.length;13    f = new int[n][k + 1];14    return dfs(0, k);15  }16private17  int dfs(int i, int k) {18    if (i >= n || k <= 0) {19      return 0;20    }21    if (f[i][k] != 0) {22      return f[i][k];23    }24    int j = search(events, events[i][1], i + 1);25    int ans = Math.max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);26    return f[i][k] = ans;27  }28private29  int search(int[][] events, int x, int lo) {30    int l = lo, r = n;31    while (l < r) {32      int mid = (l + r) >> 1;33      if (events[mid][0] > x) {34        r = mid;35      } else {36        l = mid + 1;37      }38    }39    return l;40  }41}

1class Solution {2public:3  int maxValue(vector<vector<int>> &events, int k) {4    sort(events.begin(), events.end());5    int n = events.size();6    int f[n][k + 1];7    memset(f, 0, sizeof(f));8    function<int(int, int)> dfs = [&](int i, int k) -> int {9      if (i >= n || k <= 0) {10        return 0;11      }12      if (f[i][k] > 0) {13        return f[i][k];14      }15      int ed = events[i][1], val = events[i][2];16      vector<int> t = {ed};17      int p = upper_bound(18                  events.begin() + i + 1, events.end(), t,19                  [](const auto &a, const auto &b) { return a[0] < b[0]; }) -20              events.begin();21      f[i][k] = max(dfs(i + 1, k), dfs(p, k - 1) + val);22      return f[i][k];23    };24    return dfs(0, k);25  }26};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int[][] events;4private5  int[][] f;6private7  int n;8public9  int maxValue(int[][] events, int k) {10    Arrays.sort(events, (a, b)->a[0] - b[0]);11    this.events = events;12    n = events.length;13    f = new int[n][k + 1];14    return dfs(0, k);15  }16private17  int dfs(int i, int k) {18    if (i >= n || k <= 0) {19      return 0;20    }21    if (f[i][k] != 0) {22      return f[i][k];23    }24    int j = search(events, events[i][1], i + 1);25    int ans = Math.max(dfs(i + 1, k), dfs(j, k - 1) + events[i][2]);26    return f[i][k] = ans;27  }28private29  int search(int[][] events, int x, int lo) {30    int l = lo, r = n;31    while (l < r) {32      int mid = (l + r) >> 1;33      if (events[mid][0] > x) {34        r = mid;35      } else {36        l = mid + 1;37      }38    }39    return l;40  }41}

1class Solution {2public:3  int maxValue(vector<vector<int>> &events, int k) {4    sort(events.begin(), events.end());5    int n = events.size();6    int f[n][k + 1];7    memset(f, 0, sizeof(f));8    function<int(int, int)> dfs = [&](int i, int k) -> int {9      if (i >= n || k <= 0) {10        return 0;11      }12      if (f[i][k] > 0) {13        return f[i][k];14      }15      int ed = events[i][1], val = events[i][2];16      vector<int> t = {ed};17      int p = upper_bound(18                  events.begin() + i + 1, events.end(), t,19                  [](const auto &a, const auto &b) { return a[0] < b[0]; }) -20              events.begin();21      f[i][k] = max(dfs(i + 1, k), dfs(p, k - 1) + val);22      return f[i][k];23    };24    return dfs(0, k);25  }26};

1class Solution:2    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)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.