Simple Binary search solution
Maximum Sum of Two Non-Overlapping Events\n\n## Problem Description\nGiven an array of events where each event is represented as a triplet \([s, e, v]\):  \n- \
# Maximum Sum of Two Non-Overlapping Events\n\n## Problem Description\nGiven an array of events where each event is represented as a triplet \\([s, e, v]\\):  \n- \\(s\\): Start time of the event.  \n- \\(e\\): End time of the event.  \n- \\(v\\): Value of the event.  \n\nThe goal is to find the **maximum sum of values** from two non-overlapping events.\n\n## Approach\n\n### Intuition\nTo maximize the sum of two events, we need to ensure that the two selected events do not overlap. Sorting the events by their start time enables efficient validation of the non-overlapping condition using binary search.\n\n### Algorithm\n1. **Sort Events**:  \n   Sort the events based on their start time. This simplifies finding a valid second event for a given first event.\n\n2. **Precompute Maximum Values**:  \n   Use a `maxi` array where `maxi[i]` stores the maximum event value from index \\(i\\) to the end. This allows quick retrieval of the best value for the second event.\n\n3. **Binary Search**:  \n   For each event, use binary search to find the next valid event (starting after the current event ends). Add the value of this event to the value of the current event.\n\n4. **Iterate and Update Maximum Sum**:  \n   Iterate through all events to calculate the maximum sum of values from two non-overlapping events.\n\n5. **Return the Result**:  \n   Return the maximum value obtained.\n\n---\n\n## Complexity\n\n### Time Complexity\n- Sorting the events: \\(O(n \\log n)\\).  \n- Computing the `maxi` array: \\(O(n)\\).  \n- Performing binary search for each event: \\(O(n \\log n)\\).  \n- **Total**: \\(O(n \\log n)\\).\n\n### Space Complexity\n- `maxi` array: \\(O(n)\\).  \n- Sorting space overhead: \\(O(n)\\).  \n- **Total**: \\(O(n)\\).\n\n---\n\n## Code\n```cpp\nclass Solution {\npublic:\n    int n;\n\n    int bs(int e, vector<vector<int>>& a, vector<int>& maxi) {\n        int l = 0, r = n - 1;\n        int ans = INT_MIN;\n        while (l <= r) {\n            int mid = l + (r - l) / 2;\n            if (a[mid][0] >= e) {\n                ans = maxi[mid];\n                r = mid - 1;\n            } else {\n                l = mid + 1;\n            }\n        }\n        return ans;\n    }\n\n    int maxTwoEvents(vector<vector<int>>& a) {\n        sort(a.begin(), a.end());\n        n = a.size();\n        vector<int> maxi(n, 0);\n        int ans = INT_MIN;\n\n        for (int i = n - 1; i >= 0; i--) {\n            ans = max(ans, a[i][2]);\n            maxi[i] = max(maxi[i], a[i][2]);\n            if (i + 1 < n) maxi[i] = max(maxi[i], maxi[i + 1]);\n        }\n\n        for (int i = 0; i < n; i++) {\n            int ta = a[i][2];\n            int en = a[i][1] + 1;\n            ta += bs(en, a, maxi);\n            ans = max(ans, ta);\n        }\n\n        return ans;\n    }\n};\n
['Binary Search', 'Prefix Sum', 'C++']