Maximum Number of Events That Can Be Attended II | Leetcode 1751

class Solution {
    vector<vector<int>> mem;
    vector<int> next_event;
    int n;

    int attendEvent(vector<vector<int>>& events,int pos,int k){
        if(k==0 or pos>=n)
            return 0;
        if(mem[pos][k]!=-1)
            return mem[pos][k];
        
        int skip_event = attendEvent(events,pos+1,k);

        int next = next_event[pos];
        int attend_event = attendEvent(events,next,k-1) + events[pos][2];
        return mem[pos][k] = max(skip_event,attend_event);
    }
public:
    int maxValue(vector<vector<int>>& events, int k) {
        n = events.size();
        sort(events.begin(),events.end());
        mem.assign(n,vector<int>(k+1,-1));

        next_event = vector<int>(n);
        for(int i=0;i<n;++i)
            next_event[i] = upper_bound(events.begin()+i,events.end(),vector<int>{events[i][1]+1,0,0})-events.begin();
        
        return attendEvent(events,0,k);
    }
};
/*
//JAVA
import java.util.Arrays;

class Solution {
    private int[][] mem;
    private int[] nextEvent;
    private int n;

    private int attendEvent(int[][] events, int pos, int k) {
        if (k == 0 || pos >= n) {
            return 0;
        }
        if (mem[pos][k] != -1) {
            return mem[pos][k];
        }

        int skipEvent = attendEvent(events, pos + 1, k);

        int next = nextEvent[pos];
        int attendEventVal = attendEvent(events, next, k - 1) + events[pos][2];
        return mem[pos][k] = Math.max(skipEvent, attendEventVal);
    }

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

        nextEvent = new int[n];
        for (int i = 0; i < n; ++i) {
            int left = i + 1;
            int right = n;
            while (left < right) {
                int mid = (left + right) / 2;
                if (events[mid][0] > events[i][1]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            nextEvent[i] = left;
        }

        return attendEvent(events, 0, k);
    }
}

#Python
import bisect

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        n = len(events)
        events.sort()
        mem = [[-1] * (k + 1) for _ in range(n)]
        
        next_event = [0] * n
        for i in range(n):
            left = i + 1
            right = n
            target = events[i][1] + 1
            while left < right:
                mid = (left + right) // 2
                if events[mid][0] >= target:
                    right = mid
                else:
                    left = mid + 1
            next_event[i] = left
        
        def attend_event(pos, k_remaining):
            if k_remaining == 0 or pos >= n:
                return 0
            if mem[pos][k_remaining] != -1:
                return mem[pos][k_remaining]
            
            skip_event = attend_event(pos + 1, k_remaining)
            
            next_pos = next_event[pos]
            attend_event_val = attend_event(next_pos, k_remaining - 1) + events[pos][2]
            mem[pos][k_remaining] = max(skip_event, attend_event_val)
            return mem[pos][k_remaining]
        
        return attend_event(0, k)
*/