Let come up with idea | Share thought
Intuition\n Describe your first thoughts on how to solve this problem. \nYou maybe easily find many solutions, it is not neccessary to share another solution he
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nYou maybe easily find many solutions, it is not neccessary to share another solution here but I want to share my thought how can I come up to final problem. I hope I can help you.\n\nLet start...\n\nFirstly, I think this problem must to be solved by using Dynamic Programming because I see that one event can be picked or not. So\n- I defined the state of DP likes that: `F(t, i)` which means `"maxVal" after attending "t" events which ends at "i" time`, t = [0..2], i = [1..1e9].\n- Now, if I want to find the `maximum val` after attending the `2nd event` is equal **maximum val after attending 1st event which ends before current 2nd event**: `F(2, endTime) = max(F(2, endTime), F(1, startTime-1) + 2nd_event_val)`\n\nI was happy as I thought this was a solution. I tried to implements like this:\n```\nsort events by end time\n\ndp[3][1e9]\n\nfor (t = 1 .. 2) {\n    for (event : events) {\n        startTime = event[0], endTime = event[1], val = event[2]\n\n        dp[t][endTime] = max(\n                            dp[t][endTime],\n                            dp[t-1][startTime-1] + val\n                        )\n    }\n}\n```\nBut it wrong, because I reliased that complexity is 3*1e9 :((\n\nSecondly, I think with the same idea: if choose an event as second event so I must to get the maximum val of event which ends before the current event to get the final answer. So segment tree is data structure I think to `query maximum val of events ending before the current event`. But it didn\'t work because the endTime is in range [1..1e9] it is too large (will be **Memory Limit Exceed**)\n(you can see the code segment tree at the bottom of this solution)\n\nFinnally, I come up with prefix sum, no it is not really prefix sum. I means that I use a array to maintain the maximum val of events ending before current event. And in order to `query maximum val of events ending before the current event`, I use binary search on this prefix array. \n\nAs you can see, I tight up to the idea: `query maximum val of events ending before the current event`, and try to find an efficiency way to implement this.\n\nThanks for your reading. Hope it can help u a little bit\n\n\n# Code\n# sort + prefix + binary search (Passed)\n```cpp []\n#define endTime first\n#define maxVal second\n\nclass Solution {\npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        // sort events by end time\n        sort(events.begin(), events.end(), [](auto& e1, auto& e2) {\n            return e1[1] < e2[1];\n        });\n\n        // prefix stores (endTime, maxVal): maxValue of all events ends <= endTime\n        vector<pair<int, int>> prefix;\n        int res = 0;\n        for (vector<int>& event : events) {\n            int startTime = event[0], endTime = event[1], val = event[2];\n\n            int maxValOfEventLessEndTime = bsearch(prefix, startTime-1);\n\n            res = max(res, val + maxValOfEventLessEndTime);\n            \n            int prevMax = prefix.size() > 0 ? prefix.back().maxVal : 0;\n            prefix.push_back({endTime, max(prevMax, val)});\n        }\n\n        return res;\n    }\n\n    /**\n        Find upper bound: event which has endTime <= startTime-1 param\n        Return: maxVal or 0 if can not find any event which has endTime <= startTime-1 param\n    */\n    int bsearch(vector<pair<int, int>>& prefix, int endTime) {\n        int l = 0, r = prefix.size() - 1;\n\n        int res = -1;\n        while (l <= r) {\n            int mid = l + (r - l) / 2;\n\n            if (prefix[mid].endTime <= endTime) {\n                res = mid;\n                l = mid + 1;\n            } else {\n                r = mid - 1;\n            }\n        }\n\n        if (res == -1) {\n            return 0;\n        } else {\n            return prefix[res].maxVal;\n        }\n    }\n};\n```\n\nSegment tree solution (Not passed)\n```cpp []\nclass SegmentTree {\nprivate:\n    vector<int> tree;\n    int n;\n\n    void updateTree(int node, int start, int end, int idx, int val) {\n        // Base case: if the current segment doesn\'t include the index\n        if (start > idx || end < idx) return;\n        \n        // Update the node with the maximum value\n        tree[node] = max(tree[node], val);\n        \n        // If not a leaf node, recurse on children\n        if (start != end) {\n            int mid = start + (end - start) / 2;\n            updateTree(2 * node, start, mid, idx, val);\n            updateTree(2 * node + 1, mid + 1, end, idx, val);\n        }\n    }\n\n    int queryTree(int node, int start, int end, int left, int right) {\n        // If the segment is completely outside the query range\n        if (start > right || end < left) return 0;\n        \n        // If the segment is completely inside the query range\n        if (left <= start && end <= right) return tree[node];\n        \n        // Partial overlap, recurse on children\n        int mid = start + (end - start) / 2;\n        int leftMax = queryTree(2 * node, start, mid, left, right);\n        int rightMax = queryTree(2 * node + 1, mid + 1, end, left, right);\n        \n        return max(leftMax, rightMax);\n    }\n\npublic:\n    SegmentTree(int size) {\n        n = size;\n        tree.assign(4L * n + 1, 0);\n    }\n\n    void update(int endTime, int val) {\n        updateTree(1, 1, n, endTime, val);\n    }\n\n    int query(int end) {\n        return queryTree(1, 1, n, 1, end);\n    }\n};\n\nclass Solution {\npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n          // Find the maximum end time to determine segment tree size\n        int maxEndTime = 0;\n        for (auto& event : events) {\n            maxEndTime = max(maxEndTime, event[1]);\n        }\n        \n        // Create segment tree with maximum end time\n        SegmentTree tree(maxEndTime);\n        \n        // Sort events by end time\n        sort(events.begin(), events.end(), [](auto& e1, auto& e2) {\n            return e1[1] < e2[1];\n        });\n        \n        int res = 0;\n        for (auto& event : events) {\n            // Query max value of events ending before current event starts\n            int maxPrevValue = tree.query(event[0] - 1);\n            \n            // Update maximum result\n            res = max(res, maxPrevValue + event[2]);\n            \n            // Update segment tree with current event\'s value\n            tree.update(event[1], event[2]);\n        }\n        \n        return res;\n    }\n};\n```\n\n
['Binary Search', 'Dynamic Programming', 'Segment Tree', 'Sorting', 'Prefix Sum', 'C++']