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.

&nbsp;
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.

&nbsp;
Constraints:


	1 &lt;= k &lt;= events.length
	1 &lt;= k * events.length &lt;= 106
	1 &lt;= startDayi &lt;= endDayi &lt;= 109
	1 &lt;= valuei &lt;= 106


import bisect
from functools import lru_cache

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        if k == 1: # optimization for TLE test case 57/67
            return max([event[2] for event in events])
        
        events.sort()
        event_starts = [event[0] for event in events] # enables binary search
        
        @lru_cache(None)
        def dp(i, j):
            if j == 0: # out of turns
                return 0
            if i >= len(events): # end of events array
                return 0
            max_score = events[i][2]
            
            # get minimum index where start day is greater than current end day
            next_index_minimum = bisect.bisect_left(event_starts, events[i][1] + 1)
            
            # check each possibility from the minimum next index until end of the array
            for k in range(next_index_minimum, len(events)):
                max_score = max(max_score, events[i][2] + dp(k, j - 1))
            
            # check if we can get a better score if we skip this index altogether
            max_score = max(max_score, dp(i + 1, j))
            return max_score
        return dp(0, k)
class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (e1, e2) -> (e1[0] == e2[0] ? e1[1]-e2[1] : e1[0]-e2[0]));
        return maxValue(events, 0, k, 0, new int[k+1][events.length]);
    }

    private int maxValue(int[][] events, int index, int remainingEvents, int lastEventEndDay, int[][] dp) {
        // Return 0 if no events are left or maximum choice is reached
        if (index >= events.length || remainingEvents == 0)
            return 0;

        // An Event cannot be picked if the previous event has not completed before current event
        if (lastEventEndDay >= events[index][0])
            return maxValue(events, index+1, remainingEvents, lastEventEndDay, dp);

        // Return the value if the solution is already available
        if (dp[remainingEvents][index] != 0)
            return dp[remainingEvents][index];

        // There are 2 choices that we can make,
            // SKIP this meeting or PICK this meeting
        return dp[remainingEvents][index] = Math.max(
            maxValue(events, index+1, remainingEvents, lastEventEndDay, dp), // skip
            maxValue(events, index+1, remainingEvents-1, events[index][1], dp) + events[index][2] // pick
        );
    }
}
class Solution {
public:
     
    int ans;    
    unordered_map<int,unordered_map<int,unordered_map<int,int>>> dp;
    
    int Solve(vector<vector<int>>& events, int start, int n, int k, int endtime){
        if(k == 0 || start == n){
            return 0;
        }
        
        if(dp.find(start) != dp.end() && dp[start].find(k) != dp[start].end() && dp[start][k].find(endtime) != dp[start][k].end()){
        
            return dp[start][k][endtime];
        }
        int t1 = 0;
        if(events[start][0] > endtime){
            t1 = events[start][2] + Solve(events, start+1, n, k-1, events[start][1]);
        }
        
        int t2 = Solve(events,start+1,n,k,endtime);
        
        dp[start][k][endtime] = max(t1,t2);
       // cout<< dp[start][k][endtime]<<endl;
     
        return dp[start][k][endtime];
        
    }
    int maxValue(vector<vector<int>>& events, int k) {
        
        dp.clear();
     
        // sort according to start time
        sort(events.begin(), events.end(),[](vector<int> &a,vector<int> &b){
            return a[0] < b[0];
        });
        
    return Solve(events,0,events.size(),k,0);
    
    }
};
/**
 * @param {number[][]} events
 * @param {number} k
 * @return {number}
 */
var maxValue = function(events, k) {
    events = events.sort((a, b) => a[1] - b[1]);
    const n = events.length;
    var ans = 0;
    var dp = Array.from(Array(k+1), () => new Array(n).fill(0));
    
    for(let i = 0; i < n; i++) {
        dp[1][i] = Math.max((i ? dp[1][i-1] :0), events[i][2]);
        ans = Math.max(dp[1][i], ans);
    }
    
    function binarySearch(l, r, target) {
        var pos = -1;
        while(l <= r) {
            const mid = Math.floor((l+r)/2);
            if (events[mid][1] < target) {
                pos = mid;
                l = mid+1;
            }
            else r = mid-1;
        }
        return pos;
    }
    
    for(let i = 0; i < n; i++) {
        const j = binarySearch(0, i-1, events[i][0]);
            for(let l = 2; l <= k; l++) {
                dp[l][i] = Math.max(( j >= 0 ? dp[l-1][j] + events[i][2] : 0), (i ? dp[l][i-1] : 0));
                ans = Math.max(dp[l][i], ans);
            }
    }
    
    return ans;
};
Maximum Number of Events That Can Be Attended II