Problem Description

You are given a list of events, where each event is represented as an array [startDay, endDay, value]. You can attend at most k events. For each event you attend, you must choose a day within its [startDay, endDay] interval, and you cannot attend two events on the same day. Your goal is to maximize the total value you can obtain by attending up to k events.

• You may not attend more than one event on the same day.
• You cannot attend more than k events in total.
• Each event can only be attended once.
• You must maximize the sum of the values of the attended events.

Constraints:

• 1 <= k <= events.length <= 10^4
• 1 <= startDay <= endDay <= 10^9
• 1 <= value <= 10^6

Thought Process

At first glance, the problem might look similar to the classic "Activity Selection" or "Weighted Interval Scheduling" problem, but with an added twist: you can attend up to k events, and each event has a value. The brute-force approach would be to try every combination of up to k events and select the one with the highest total value, but this quickly becomes infeasible due to the exponential number of combinations.

To optimize, we can recognize that:

• Each event can be attended on any day in its interval, but to avoid conflicts, we can't overlap days.
• We want to select a non-overlapping set of up to k events with maximum total value.
• This hints at using dynamic programming, combined with binary search, to efficiently decide which events to pick.

Solution Approach

We use a combination of dynamic programming (DP) and binary search to solve the problem efficiently:

1. Sort Events:
   • Sort the events by their startDay. This allows us to process them in order and use binary search to find the next available event.
2. Dynamic Programming State:
   • Let dp[i][j] represent the maximum value obtainable by considering the i-th event and attending up to j events.
   • For memory efficiency, we can use memoization and recursion, or iterative DP with two dimensions.
3. Transition:
   • At each event, we have two choices:
     • Skip the event: dp[i+1][j]
     • Attend the event: Add the event's value, and move to the next event that starts after the current event's endDay (found via binary search), decrementing j by 1: value + dp[next][j-1]
   • The answer is the maximum of these two choices.
4. Binary Search:
   • For each event, use binary search to find the next event whose startDay is after the current event's endDay.
5. Base Cases:
   • If we've attended k events or reached the end of the event list, return 0.

This approach ensures we never consider overlapping events and always maximize the sum of values.

Example Walkthrough

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

1. Sort Events:
   • Events already sorted: [[1,2,4],[2,3,1],[3,4,3]]
2. First Event (index 0, [1,2,4]):
   • Option 1: Skip, move to index 1 with k=2.
   • Option 2: Attend, value=4. Use binary search to find the next event starting after day 2 (index 2, [3,4,3]). Now k=1.
3. Second Event (index 1, [2,3,1]):
   • Option 1: Skip, move to index 2 with k=2.
   • Option 2: Attend, value=1. Next event after day 3 is index 3 (out of bounds). Now k=1.
4. Third Event (index 2, [3,4,3]):
   • Option 1: Skip, move to index 3 with k=2 (base case, return 0).
   • Option 2: Attend, value=3. Next event after day 4 is index 3 (out of bounds). Now k=1.
5. Recursive Calculation:
   • Best is to attend events 0 and 2: 4 + 3 = 7.
   • Alternatively, attending events 1 and 2: 1 + 3 = 4.
   • Or events 0 and 1: 4 + 1 = 5.
   • Maximum is 7.

Time and Space Complexity

• Brute-force:
  • Time: O(2^n), since for each event you can choose to attend or skip.
  • Space: O(n), for recursion stack.
• Optimized DP + Binary Search:
  • Let n be the number of events and k the maximum events you can attend.
  • Time: O(nk log n), since for each of the n events and k choices, we do a binary search (log n) to find the next event.
  • Space: O(nk), for the DP memoization table.

Summary

This problem is a variation of the weighted interval scheduling problem, extended to allow attending up to k events. By sorting the events, using binary search to efficiently find the next non-overlapping event, and applying dynamic programming to avoid redundant computations, we achieve an efficient solution. The key insight is modeling the problem with a recursive DP that tracks both the event index and the count of events attended, ensuring we never double-book a day and always maximize the total value.

Code Implementation

from bisect import bisect_right
from functools import lru_cache

class Solution:
    def maxValue(self, events, k):
        # Sort by start day
        events.sort()
        n = len(events)
        # Precompute next indices using binary search
        starts = [e[0] for e in events]
        
        @lru_cache(None)
        def dp(i, attended):
            if attended == k or i == n:
                return 0
            # Option 1: Skip current event
            res = dp(i+1, attended)
            # Option 2: Attend current event
            # Find next event whose start is after current end
            next_i = bisect_right(starts, events[i][1])
            res = max(res, events[i][2] + dp(next_i, attended+1))
            return res
        
        return dp(0, 0)
      

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        sort(events.begin(), events.end());
        int n = events.size();
        vector<int> starts(n);
        for (int i = 0; i < n; ++i) starts[i] = events[i][0];
        // dp[i][attended]: max value starting at i, attended events so far
        vector<vector<int>> dp(n+1, vector<int>(k+1, -1));
        
        function<int(int, int)> dfs = [&](int i, int attended) {
            if (attended == k || i == n) return 0;
            if (dp[i][attended] != -1) return dp[i][attended];
            // Option 1: skip
            int res = dfs(i+1, attended);
            // Option 2: take
            int next_i = upper_bound(starts.begin(), starts.end(), events[i][1]) - starts.begin();
            res = max(res, events[i][2] + dfs(next_i, attended+1));
            return dp[i][attended] = res;
        };
        return dfs(0, 0);
    }
};
      

import java.util.*;

class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
        int n = events.length;
        int[] starts = new int[n];
        for (int i = 0; i < n; ++i) starts[i] = events[i][0];
        Integer[][] memo = new Integer[n][k+1];

        return dfs(events, starts, 0, 0, k, memo);
    }

    private int dfs(int[][] events, int[] starts, int i, int attended, int k, Integer[][] memo) {
        if (attended == k || i == events.length) return 0;
        if (memo[i][attended] != null) return memo[i][attended];
        // Option 1: skip
        int res = dfs(events, starts, i+1, attended, k, memo);
        // Option 2: take
        int next = upperBound(starts, events[i][1]);
        res = Math.max(res, events[i][2] + dfs(events, starts, next, attended+1, k, memo));
        memo[i][attended] = res;
        return res;
    }

    private int upperBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] <= target) low = mid + 1;
            else high = mid;
        }
        return low;
    }
}
      

var maxValue = function(events, k) {
    events.sort((a, b) => a[0] - b[0]);
    let n = events.length;
    let starts = events.map(e => e[0]);
    let memo = Array.from({length: n}, () => Array(k+1).fill(undefined));

    function upperBound(arr, target) {
        let low = 0, high = arr.length;
        while (low < high) {
            let mid = Math.floor((low + high) / 2);
            if (arr[mid] <= target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    function dfs(i, attended) {
        if (attended === k || i === n) return 0;
        if (memo[i][attended] !== undefined) return memo[i][attended];
        // Option 1: skip
        let res = dfs(i+1, attended);
        // Option 2: take
        let next = upperBound(starts, events[i][1]);
        res = Math.max(res, events[i][2] + dfs(next, attended+1));
        memo[i][attended] = res;
        return res;
    }
    return dfs(0, 0);
};