1
class Solution {
2
  public int maxTwoEvents(int[][] events) {
3
    Arrays.sort(events, (a, b) -> a[0] - b[0]);
4
    int onRight = 0, maxOne = 0, n = events.length;
5
    int[] rightMax = new int[n + 1];
6
    for (int i = n - 1; i >= 0; i--) {
7
      int start = events[i][0], end = events[i][1], val = events[i][2];
8
      maxOne = Math.max(val, maxOne);
9
      rightMax[i] = Math.max(rightMax[i + 1], val);
10
    }
11
    int two = 0;
12
    for (int i = 0; i < n; i++) {
13
      int start = events[i][0], end = events[i][1], val = events[i][2];
14
      int idx = binarySearch(end, events);
15
      if (idx < n) {
16
        two = Math.max(rightMax[idx] + val, two);
17
      }
18
    }
19
    return Math.max(two, maxOne);
20
  }
21

22
  public int binarySearch(int end, int[][] arr) {
23
    int left = 0, right = arr.length;
24
    while (left < right) {
25
      int mid = left + (right - left) / 2;
26
      if (arr[mid][0] > end) {
27
        right = mid;
28
      } else {
29
        left = mid + 1;
30
      }
31
    }
32
    return left;
33
  }
34
}