Java O(nlogn) Binary Search + Maximum Caching
We only need to find a pair of non-overlapping events. Therefore, given one fixed event, we need to find the other event with non-overlapping to form a pair. Fo
We only need to find a pair of non-overlapping events. Therefore, given one fixed event, we need to find the other event with non-overlapping to form a pair. For each pair, we calculate the maximum. However, the complexity will be O(n^2).\n\nTo reduce the complexity, we use binary search to find the other event without overlapping. We first sort the events array based on the starting time. Given a fixed event, once the starting time is sorted, we can use binary search to find the non-overlapping event to form the pair. Moreover, we need an array maxArr to record the maximum value of every event so that we only need O(1) to index.\n\nThe codes are as follows:\n```\n\nclass Solution {\n\n    public int maxTwoEvents(int[][] events) {\n        if(events == null || events.length < 1) {\n            return 0;\n        }\n\t\t\n\t\t// Sort the event array based on the starting time\n        Arrays.sort(events, (a, b) -> a[0] == b[0] ? b[2] - a[2] : a[0] - b[0]);\n        \n\t\t// Use an array to record the maximum value\n        int[] maxArr = new int[events.length];\n        \n        maxArr[events.length - 1] = events[events.length - 1][2];\n        for(int i = events.length - 2; i >= 0; i--) {\n            maxArr[i] = Math.max(maxArr[i + 1], events[i][2]);\n        }\n        \n\t\t// The current maximum value is the last event\n        int ans = events[events.length - 1][2];\n        \n        for(int i = 0; i < events.length - 1; i++) {\n            int index = find(events, events[i][1], i + 1);\n            \n            if(index == -1) {\n\t\t\t// If we cannot find a non-overlapping event, the maximum so far is the current event value\n                ans = Math.max(ans, events[i][2]);\n            } else {\n\t\t\t// The maximum is the current event value plus the nonoverlapping event value\n                ans = Math.max(ans, events[i][2] + maxArr[index]);\n            }\n        }\n        \n        return ans;\n    }\n    \n    private int find(int[][] events, int target, int left) {\n\t// Binary search to find the first nonoverlapping event\n        int right = events.length - 1;\n        \n        while(left + 1 < right) {\n            int mid = left + (right - left) / 2;\n            \n            if(events[mid][0] <= target) {\n                left = mid;\n            } else {\n                right = mid;\n            }\n        }\n        \n        if(events[left][0] > target) {\n            return left;\n        }\n        \n        if(events[right][0] > target) {\n            return right;\n        }\n        \n        return -1;\n    }\n}\n```
['Sorting', 'Binary Tree', 'Java']