Count Integers in Intervals LeetCode solution in Java

1
class CountIntervals {
2

3
  // for storing intervals
4
  TreeMap<Integer, Integer> map = new TreeMap<>();
5
  int count = 0;
6

7
  public CountIntervals() {}
8

9
  public void add(int left, int right) {
10
    // we are taking left side as reference and calculating ans
11

12
    // this is the current length
13
    int add = right - left + 1;
14

15
    // var is the default data type
16
    // lowerentry gives the value of smaller(smaller largest) entry compared to (left+1)
17
    // we added +1 bcz there may be a case where left is present in a map
18
    // lowerentry gives the  value(that is)<left+1
19
    var left_bound = map.lowerEntry(left + 1);
20

21
    // if there is some value present then go
22
    // getvalue gives the right positon
23
    // if current left is cover under map.right value means there is a overlap
24
    if (left_bound != null && left_bound.getValue() >= left) {
25
      // positions are map.left <= left <= min(map.right,right) <= max(map.right,right)
26

27
      // examples:   (1)                       (2)                     (3)
28
      //       ____________                 _________            _______________     (map)
29
      //                ___________                  ________           ____         (our)
30

31
      // now, left become the smallest value which in this case is map.left
32
      left = left_bound.getKey();
33

34
      // same as right become the maximum value
35
      right = Math.max(left_bound.getValue(), right);
36

37
      // value overlap means curr answer(add) also change
38
      // we already calculated the map value (covered area) and added into ans variable
39
      // calculate/add the new uncovered value
40
      //    right            - map.right
41
      // max(right,map.right) - map.right
42
      // we are not adding +1 bcz that is already handled by overlaping area
43
      add = right - left_bound.getValue();
44

45
      // this is taken so we have to remove
46
      // at last we added the largest area (which is stored int left,right)
47
      map.remove(left_bound.getKey());
48
    }
49

50
    // check is right overlaping
51
    // if yes then take the correct values
52
    // higherEntry gives the largest(largest smallest) value in map
53
    // we are not taking left+1 bcz that condition is already been satisfied
54
    // eg. left=5 map contains (5,value)
55
    // condition is checked in left_bound
56
    // i.getKey()<=right means curr is beneath our map.left and covering area(overlaping)
57
    for (var i = map.higherEntry(left);
58
        i != null && i.getKey() <= right;
59
        i = map.higherEntry(left)) {
60
      // left <= map.left <= min(right,map.right) <= max(right,map.right)
61

62
      // examples:   (1)                       (2)                         (3)
63
      //            ____________                _________              _______             (map)
64
      //     ___________                ________                 _________________         (our)
65

66
      // now we have our add which is current ans but some area is overlaping
67
      // so we have to subtract overlaping area
68
      // +1 bcz [2,5] we have 4 position (2,3,4,5) ; 5-2=>3 ; we ned to add 1
69
      add -= Math.min(right, i.getValue()) - i.getKey() + 1;
70

71
      // right value become the largest among them
72
      right = Math.max(right, i.getValue());
73

74
      // we have taken care this entry and calculated left and right now we don't need
75
      map.remove(i.getKey());
76
    }
77

78
    // we pushed the values
79
    // this entry can be essential for next calls
80
    map.put(left, right);
81

82
    // add the current ans
83
    count += add;
84
  }
85

86
  public int count() {
87
    return count;
88
  }
89
}
90

91
/**
92
 * Your CountIntervals object will be instantiated and called as such: CountIntervals obj = new
93
 * CountIntervals(); obj.add(left,right); int param_2 = obj.count();
94
 */