[ C++ | Java | Kotlin ] Simple binary search solution, detailed explanation, beats 100% 🚀
Intuition\nThe key insight is that since we can only select up to two non-overlapping events, we can:\n1. First sort the events by start time to make it easier 
# Intuition\nThe key insight is that since we can only select up to two non-overlapping events, we can:\n1. First sort the events by start time to make it easier to find non-overlapping pairs\n2. For each event, try to pair it with the best possible non-overlapping event that comes after it\n3. Use preprocessing to quickly find the maximum value available after any given point\n\n# Approach\n1. Sort Events:\n   - Sort all events by their start time to establish a clear timeline\n   - This makes it easier to find non-overlapping events since we know all potential second events must start after the first one ends\n\n2. Precompute Maximum Values (maxSuffix array):\n   - Create an array that stores the maximum value achievable from each position onwards\n   - For each position i, maxSuffix[i] = max(current event value, maxSuffix[i+1])\n   - This lets us quickly find the best possible second event after any point\n\n3. Binary Search for Non-overlapping Events:\n   - For each event, we need to find the first event that starts after this event ends\n   - Use binary search since the events are sorted by start time\n   - This is much more efficient than checking each subsequent event ($$O(log(n)$$) vs $$O(n)$$)\n\n4. Calculate Maximum Value:\n   - For each event i:\n     * Take its value\n     * Find the first non-overlapping event after it using binary search\n     * Add the maximum possible value from that point (using maxSuffix)\n   - Keep track of the maximum sum found\n\n# Complexity\nTime Complexity: $$O(n * log(n))$$ where n is the number of events\n- Sorting: $$O(n * log(n))$$\n- Creating maxSuffix: $$O(n)$$\n- For each event, binary search: $$O(n * log(n))$$\n\nSpace Complexity: $$O(n)$$ for the maxSuffix array\n\nThis solution efficiently handles the constraints of non-overlapping events while finding the maximum possible value using two key optimizations: precomputed maximum values and binary search for finding valid pairs.\n\n# Code\n```kotlin []\nclass Solution {\n    fun maxTwoEvents(events: Array<IntArray>): Int {\n        events.sortBy { it.first() }\n        val n = events.size\n        val maxSuffix = IntArray(n)\n        maxSuffix[n - 1] = events[n - 1].last()\n        for (i in n - 2 downTo 0) {\n            maxSuffix[i] = max(maxSuffix[i + 1], events[i].last())\n        }\n\n        fun binSearch(left: Int, right: Int, target: Int): Int {\n            if (left >= right) return right\n            val mid = left + (right - left) / 2\n            return if (events[mid].first() > target) binSearch(left, mid, target) else binSearch(mid + 1, right, target)\n        }\n\n        return events.indices.maxOf { i ->\n            events[i].last() + binSearch(i + 1, n, events[i][1]).let { if (it < n) maxSuffix[it] else 0 }\n        }\n    }\n}\n```\n```java []\nclass Solution {\n    public int maxTwoEvents(int[][] events) {\n        Arrays.sort(events, Comparator.comparingInt(a -> a[0]));\n        \n        int n = events.length;\n        int[] maxSuffix = new int[n];\n        \n        maxSuffix[n - 1] = events[n - 1][2];\n        for (int i = n - 2; i >= 0; i--) {\n            maxSuffix[i] = Math.max(maxSuffix[i + 1], events[i][2]);\n        }\n        \n        int maxValue = 0;\n        for (int i = 0; i < n; i++) {\n            int currentValue = events[i][2];\n            int nextEventIndex = binSearch(i + 1, n, events[i][1], events);\n            int additionalValue = (nextEventIndex < n) ? maxSuffix[nextEventIndex] : 0;\n            maxValue = Math.max(maxValue, currentValue + additionalValue);\n        }\n        \n        return maxValue;\n    }\n    \n    private int binSearch(int left, int right, int target, int[][] events) {\n        if (left >= right) {\n            return right;\n        }\n        \n        int mid = left + (right - left) / 2;\n        if (events[mid][0] > target) {\n            return binSearch(left, mid, target, events);\n        } else {\n            return binSearch(mid + 1, right, target, events);\n        }\n    }\n}\n```\n```cpp []\nclass Solution {\nprivate:\n    int binSearch(int left, int right, int target, const vector<vector<int>>& events) {\n        if (left >= right) {\n            return right;\n        }\n        \n        int mid = left + (right - left) / 2;\n        if (events[mid][0] > target) {\n            return binSearch(left, mid, target, events);\n        } else {\n            return binSearch(mid + 1, right, target, events);\n        }\n    }\n    \npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin(), events.end(), \n             [](const vector<int>& a, const vector<int>& b) {\n                 return a[0] < b[0];\n             });\n        \n        int n = events.size();\n        vector<int> maxSuffix(n);\n        \n        maxSuffix[n - 1] = events[n - 1][2];\n        for (int i = n - 2; i >= 0; i--) {\n            maxSuffix[i] = max(maxSuffix[i + 1], events[i][2]);\n        }\n        \n        int maxValue = 0;\n        for (int i = 0; i < n; i++) {\n            int currentValue = events[i][2];\n            int nextEventIndex = binSearch(i + 1, n, events[i][1], events);\n            int additionalValue = (nextEventIndex < n) ? maxSuffix[nextEventIndex] : 0;\n            maxValue = max(maxValue, currentValue + additionalValue);\n        }\n        \n        return maxValue;\n    }\n};\n```\n![image.png](https://assets.leetcode.com/users/images/ee3c9810-ae34-442b-853c-2522ad405d54_1733671898.5396173.png)\n
['Array', 'Binary Search', 'Sorting', 'C++', 'Java', 'Kotlin']