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

// class Solution {
// public:
// unordered_map<string,int> dp;
// vector<vector<int>> v;
//     static bool cmp(vector<int> &a,vector<int> &b){
//         return a[0]<b[0];
//     }

//     int solverec(vector<int> &arr,int n,int i,int k){
//         if(i>=n)return 0;
//         if(k==0)return 0;
//         string key = to_string(i)+" "+to_string(k);
//         if(dp.find(key)!=dp.end()) return dp[key];
//         int op=0;
//         op=max(solverec(arr,n,i+1,k),op);
//         int val = v[i][2];
//         int newind = upper_bound(arr.begin(),arr.end(),v[i][1])-arr.begin();
//         op=max(op,val+solverec(arr,n,newind,k-1));
//         return dp[key]= op;
//     }

//     int maxValue(vector<vector<int>>& events, int k) {
//         int n = events.size();
//         v=events;
//         sort(v.begin(),v.end(),cmp);
//         //cant start the event that ends on same day => upper_bound
//         vector<int> arr;
//         for(auto i:v){
//             arr.push_back(i[0]);
//         }
//         return solverec(arr,n,0,k);
//     }
// };
class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        int n = events.size();
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        sort(events.begin(), events.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] < b[0];
        });

        // Extract the start times for binary search
        vector<int> startTimes;
        for (auto& event : events) {
            startTimes.push_back(event[0]);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = 1; j <= k; ++j) {
                // Option 1: Skip the current event
                dp[i][j] = dp[i + 1][j];
                
                // Option 2: Include the current event
                int nextIndex = upper_bound(startTimes.begin(), startTimes.end(), events[i][1]) - startTimes.begin();
                dp[i][j] = max(dp[i][j], events[i][2] + dp[nextIndex][j - 1]);
            }
        }

        return dp[0][k];
    }
};

113848