Simple Solution With Added Comments | Binary Search | Sorting | Time Complexity O(nlogn) |
Intuition\nThe solution aims to maximize the sum of values from two non-overlapping events. Events are sorted by start time for efficient binary search. A right
# Intuition\nThe solution aims to maximize the sum of values from two non-overlapping events. Events are sorted by start time for efficient binary search. A right-max array (`rmax`) stores the maximum value of events to the right. For each event, binary search finds the next non-overlapping event, and their values are combined to compute the maximum sum.\n\n# Approach\n### Approach to Solve the Problem:\n\n1. **Sort Events by Start Time**:  \n   - Sort the events based on their start time to facilitate efficient binary search for non-overlapping intervals.\n\n2. **Create a Right-Max Array `rmax`**:  \n   - Traverse the events from right to left to compute `rmax`, where `rmax[i]` stores the maximum value of events from index `i` to the end.\n\n3. **Binary Search for Non-Overlapping Events**:  \n   - For each event, use binary search to find the next event that starts after the current event\'s end time.\n\n4. **Calculate Maximum Value for Two Events**:  \n   - For each event, calculate the sum of its value and the maximum value (`rmax`) of the non-overlapping event found using binary search.\n\n5. **Track the Overall Maximum**:  \n   - Update the result with the maximum sum calculated for each event pair.\n\n6. **Return the Result**:  \n   - Return the highest sum of values from two non-overlapping events.\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    // Time Complexity: O(n log n) (due to sorting and binary search in a loop)\n    // Space Complexity: O(n) (for storing the rmax array)\n\n    // Binary Search to find the first event whose start time is greater than\n    // the end time of the current event\n    int bs(int i, vector<vector<int>>& events, int n) {\n        int low = i + 1;\n        int high = n - 1;\n        int mid;\n        int ind = -1; // Initialize result as -1 (indicating no suitable event found)\n        while (low <= high) {\n            mid = low + (high - low) / 2;\n            if (events[mid][0] > events[i][1]) {\n                ind = mid;\n                high = mid - 1;\n            } else {\n                low = mid + 1;\n            }\n        }\n        return ind;\n    }\n\n    int maxTwoEvents(vector<vector<int>>& events) {\n        int n = events.size();\n        // Sort events based on their start time\n        // Sorting ensures we can use binary search to find non-overlapping\n        // events efficiently\n        sort(events.begin(), events.end());\n\n        // Create an array rmax to store the maximum value of events from the\n        // current index to the end\n        vector<int> rmax(n, INT_MIN);\n        int maxi = INT_MIN;\n        for (int i = n - 1; i >= 0; i--) {\n            maxi = max(maxi, events[i][2]);\n            rmax[i] = maxi;\n        }\n\n        // Iterate over each event and calculate the maximum value achievable by\n        // selecting two non-overlapping events\n        int ans = 0;\n        int ind; // To store the index of the next non-overlapping event\n        for (int i = 0; i < n; i++) {\n            ind = bs(i, events, n);\n            int val = events[i][2]; // Value of the current event\n            if (ind != -1)\n                val += rmax[ind]; // Add the maximum value from the right if a\n                                  // valid index is found\n            ans = max(ans, val);\n        }\n        return ans;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n\n```
['C++']