<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:
    /*
        there are 2 options: participate or not (1 or 0)
        [1, 2, 10], [2, 4, 1], [5, 6, 1]


        dp[i] is the max value that we can get if we choose the event i at the end.
        dp[i] = max(dp[j]) (satisfy constraints) + value[i];

        O(n^2)


        segment tree to store the largest value O(logn)


    */

    int findLastValid(int i, vector<vector<int>>& events) {
        auto pos = lower_bound(events.begin(), events.begin() + i + 1, events[i][0], [](const vector<int>& a, int target) { // lower_bound incorrect target
            return a[1] < target;  // wrong comparator
        });
        if (pos == events.begin()) {
            return -1;
        }

        return prev(pos) - events.begin();
    }

    int maxValue(vector<vector<int>>& events, int k) {
        int dp[k + 1][events.size() + 1]; // dp[3][4];

        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        // [[1,2,4],[2,3,1],[3,4,3]]

        for(int i = 0; i < events.size(); i++) {
            if (i == 0) {
                dp[1][i] = events[i][2];
            } else {
                dp[1][i] = max(events[i][2], dp[1][i - 1]); // forgot base case
            }
            
        }

        // i = 2
        // dp[1] = [4,1,3]
        // dp[2] = [4,1,7]

        for(int time = 2; time <= k; time++) {
            for(int i = 0; i < events.size(); i++) {
                if (i > 0) {
                    int j = findLastValid(i, events);
                    if (j == -1) {
                        dp[time][i] = max(dp[time - 1][i], dp[time][i - 1]);  // forgot optimized case
                    } else {
                        dp[time][i] = max(dp[time - 1][j] + events[i][2], dp[time][i - 1]); // forget adding cost
                    }
                } else {
                    dp[time][i] = dp[time - 1][i];
                }       
            }
        }
        
        return dp[k][events.size() - 1];
    }
};
89271