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

#define pp pair<int,int>
class Solution {
public:
int find_index(int start,vector<vector<int>> &arr,int end,int target){
    int ans = end+1;
    while(start<=end){
          int mid = (start+end)/2;
          if(arr[mid][0]>=target){
            ans = mid;
            end = mid-1;
          }
          else{
            start = mid+1;
          }
    }
    return ans;
}
int solve(vector<vector<int>> &events,int k,int index,int end){
    if(index>=events.size()||k==0){
        return 0;
    }
    if(events[index][0]>end){
        int ans1 = solve(events,k-1,index+1,events[index][1])+events[index][2];
        int ans2 = solve(events,k,index+1,end);
        return max(ans1,ans2);
    }
    return solve(events,k,index+1,end);

}
    int maxValue(vector<vector<int>>& events, int k) { 
        sort(events.begin(),events.end());
       // return solve(events,k,0,0)
       int n = events.size();
       int dp[n+1][k+1];
       for(int i =0;i<=n;i++){
            dp[i][k] = 0;
       }
       for(int i =0;i<=k;i++){
        dp[n][i] = 0;
       }
       for(int i = n-1;i>=0;i--){
        for(int j = k-1;j>=0;j--){

            int ind = find_index(i,events,n-1,events[i][1]+1);
            
          dp[i][j] = max(dp[i+1][j],dp[ind][j+1]+events[i][2]);
        }
       }
return dp[0][0];


           




        //   set<int> st;
        //   unordered_map<int,int> mp;
        //   sort(events.begin(),events.end());
        //   int max_sum = 0;
        //   int max_val = 0;
        //   for(int i =0;i<events.size();i++){
        //        int start1 = events[i][0];
        //        int end1 =events[i][1];
        //        int val = events[i][2];
        //        auto it = st.lower_bound(start1);
        //        if(it==st.end()&&st.size()!=0){
        //         it--;
        //            max_val = max(max_val,mp[*it]+val);
        //            st.insert(end1);
        //            mp[end1] = mp[*it]+val;
        //        }
        //        else if(it!=st.begin()){
        //             it--;  
        //             max_val = max(max_val,mp[*it]+val);
        //             st.insert(end1);
        //                 mp[end1] = mp[*it]+val;
        //         }
        //         else{
        //            max_val = max(max_val,val);
        //                 st.insert(end1);
        //                     mp[end1] = val;
        //         }            
        //   }
        //   return max_val;
    }
};
90966