Binary Search & Suffix Array
Intuition\nThe basic idea is that for every event, the result can either be the current event\'s value or the current event\'s value plus the maximum value of s
# Intuition\nThe basic idea is that for every event, the result can either be the current event\'s value or the current event\'s value plus the maximum value of some future non-overlapping event. To efficiently find the next non-overlapping event, we can jump directly to the interval that starts after the current one ends. After that, we can continue linearly.\n\nTo optimize this process, we can use a suffix array. The suffix array stores the maximum value from the current event until the end, allowing us to quickly look up the best future event without having to scan through all future events.\n\n# Complexity\n- Time complexity:\nO(N*Log(N))\n\n- Space complexity:\nO(N)\n\n\n# Code\n```java []\nclass Solution {\n    private int upperBound(int lo, int [][] events, int target) {\n        int hi = events.length - 1;\n        while (lo <= hi) {\n            int mid = lo + ((hi - lo) >> 1);\n            if (events[mid][0] <= target) {\n                lo = mid + 1;\n            } else {\n                hi = mid - 1;\n            }\n        } \n        return lo;\n    }\n    public int maxTwoEvents(int[][] events) {\n        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));\n        int [] dp = new int [events.length];\n        dp[events.length - 1] = events[events.length - 1][2];\n        for (int i = events.length - 2; i >= 0; i--) {\n            dp[i] = Math.max(dp[i + 1], events[i][2]);\n        }\n        int result = dp[0];\n        for (int i = 0; i < events.length; ++i) {\n            int j = upperBound(i + 1, events, events[i][1]);\n            if (j < events.length ) {\n                result = Math.max(result, dp[j] + events[i][2]);\n            }   \n        }\n        return result;\n    }\n}\n```
['Java']