<p>You are given an array of <code>events</code> where <code>events[i] = [startDay<sub>i</sub>, endDay<sub>i</sub>, value<sub>i</sub>]</code>. The <code>i<sup>th</sup></code> event starts at <code>startDay<sub>i</sub></code><sub> </sub>and ends at <code>endDay<sub>i</sub></code>, and if you attend this event, you will receive a value of <code>value<sub>i</sub></code>. You are also given an integer <code>k</code> which represents the maximum number of events you can attend.</p>

<p>You can only attend one event at a time. If you choose to attend an event, you must attend the <strong>entire</strong> event. Note that the end day is <strong>inclusive</strong>: that is, you cannot attend two events where one of them starts and the other ends on the same day.</p>

<p>Return <em>the <strong>maximum sum</strong> of values that you can receive by attending events.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60048-pm.png" style="width: 400px; height: 103px;" /></p>

<pre>
<strong>Input:</strong> events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
<strong>Output:</strong> 7
<strong>Explanation: </strong>Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60150-pm.png" style="width: 400px; height: 103px;" /></p>

<pre>
<strong>Input:</strong> events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
<strong>Output:</strong> 10
<strong>Explanation:</strong> Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do <strong>not</strong> have to attend k events.</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-60703-pm.png" style="width: 400px; height: 126px;" /></strong></p>

<pre>
<strong>Input:</strong> events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
<strong>Output:</strong> 9
<strong>Explanation:</strong> Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= events.length</code></li>
	<li><code>1 &lt;= k * events.length &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= startDay<sub>i</sub> &lt;= endDay<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= value<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
</ul>

bool customSort(vector<int>&a, vector<int>& b){
    if(a[0]<b[0]){
        return true;
    }
    else if(a[0]>b[0]){
        return false;
    }
    else{
        //Equal
        return a[1]<b[1];
    }
}
class Solution {
    int checkNonOverlap(vector<vector<int>>& events, int idx){
        int start = events[idx][0];
        int end = events[idx][1];
        idx++;
        while(idx<events.size()){
            if(end>=events[idx][0]){
                idx++;
            }
            else{
                break;
            }
        }
        return idx;

        // int end = events[idx][0];
        // int left =idx+1;
        // int right = events.size();
        // while(left<right){
        //     int mid = (left+right)/2;
        //     if(end <=events[mid][0]){
        //         left = mid+1;
        //     }
        //     else{
        //         right = mid;
        //     }
        // }
        // return right-1;
    }
    int eventUtils(vector<vector<int>>& events, vector<int>& newIndices, int k, int idx, vector<vector<int>>& dp){
        if(idx>=events.size()|| k<=0){
            return 0;
        }
        if(dp[idx][k-1]!=-1){
            return dp[idx][k-1];
        }
        // int newIdx = checkNonOverlap(events, idx);
        // int target = events[idx][1];
        // auto it = upper_bound(starts.begin(), starts.end(), target);
        // int newIdx = it-starts.begin();
        int newIdx = newIndices[idx];
        int curr = events[idx][2] + eventUtils(events, newIndices, k-1, newIdx, dp);
        int notCurr = eventUtils(events, newIndices, k, idx+1, dp);
        dp[idx][k-1] = max(curr, notCurr);
        return dp[idx][k-1];
    }
public:
    int maxValue(vector<vector<int>>& events, int k) {
        sort(events.begin(), events.end(), customSort);
        
        
        int n = events.size();
        vector<int> starts;
        for(int i=0;i<n;i++){
            starts.push_back(events[i][0]);
        }
        vector<int> newIndices;
        for(int i=0;i<n;i++){
            int newIdx = upper_bound(starts.begin(), starts.end(), events[i][1]) - starts.begin();
            newIndices.push_back(newIdx);
        }
        // vector<vector<int>> dp(n, vector<int>(k, -1));
        // return eventUtils(events, newIndices, k, 0, dp);

        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
        // dp[n][i]=dp[j][0]=0;

        for(int i=n-1;i>=0;i--){
            for(int j=k-1;j>=0;j--){
                int newIdx = newIndices[i];
                dp[i][j] = max(events[i][2]+dp[newIdx][j+1], dp[i+1][j]);
            }
        }
        return dp[0][0];

    }
};
116391