Count Number of Rectangles Containing Each Point LeetCode solution in Java

1
class Solution {
2
  public int[] countRectangles(int[][] rectangles, int[][] points) {
3
    int max = Integer.MIN_VALUE;
4

5
    TreeMap<Integer, List<Integer>> rects = new TreeMap<>();
6
    for (int[] rect : rectangles) {
7
      if (!rects.containsKey(rect[1])) {
8
        rects.put(rect[1], new ArrayList<Integer>());
9
      }
10

11
      rects.get(rect[1]).add(rect[0]);
12
      max = Math.max(max, rect[1]);
13
    }
14

15
    for (int k : rects.keySet()) {
16
      Collections.sort(rects.get(k));
17
    }
18

19
    int[] ans = new int[points.length];
20
    for (int i = 0; i < points.length; i++) {
21
      if (points[i][1] > max) {
22
        continue;
23
      }
24

25
      int count = 0;
26

27
      for (int key : rects.subMap(points[i][1], max + 1).keySet()) {
28
        List<Integer> y = rects.get(key);
29

30
        count += binarySearch(y, points[i][0]);
31
      }
32

33
      ans[i] = count;
34
    }
35

36
    return ans;
37
  }
38

39
  private int binarySearch(List<Integer> vals, int val) {
40
    int lo = 0;
41
    int hi = vals.size() - 1;
42
    int id = -1;
43

44
    while (lo <= hi) {
45
      int mid = lo + (hi - lo) / 2;
46

47
      if (vals.get(mid) < val) {
48
        lo = mid + 1;
49
      } else {
50
        id = mid;
51
        hi = mid - 1;
52
      }
53
    }
54

55
    if (id < 0) {
56
      return 0;
57
    }
58

59
    return vals.size() - id;
60
  }
61
}