1
class RangeModule {
2
  TreeMap<Integer, Integer> map;
3

4
  public RangeModule() {
5
    map = new TreeMap<>();
6
  }
7

8
  public void addRange(int left, int right) {
9
    // assume the given range [left, right), we want to find [l1, r1) and [l2, r2) such that l1 is
10
    // the floor key of left, l2 is the floor key of right. Like this:
11
    // [left, right)
12
    // [l1, r1) [l2, r2)
13
    // Note: l2 could be the same as l1, so they are either both null or both non-null
14
    Integer l1 = map.floorKey(left);
15
    Integer l2 = map.floorKey(right);
16

17
    // try to visualize each case, and what to do based on r1
18
    if (l1 == null && l2 == null) {
19
      map.put(left, right);
20
    } else if (l1 != null && map.get(l1) >= left) {
21
      map.put(
22
          l1,
23
          Math.max(
24
              right, map.get(l2))); // r2 will always be greater than r1, so no need to check r1
25
    } else {
26
      map.put(left, Math.max(right, map.get(l2)));
27
    }
28

29
    // we don't want to remove the range starts at left, so left should be exclusive.
30
    // but we want to remove the one starts at right, so right should be inclusive.
31
    map.subMap(left, false, right, true).clear();
32
  }
33

34
  public boolean queryRange(int left, int right) {
35
    Integer l = map.floorKey(left);
36
    if (l != null && map.get(l) >= right) {
37
      return true;
38
    }
39
    return false;
40
  }
41

42
  public void removeRange(int left, int right) {
43
    Integer l1 =
44
        map.lowerKey(
45
            left); // I used lowerKey here, since we don't care about the range starting at left, as
46
    // it should be removed
47
    Integer l2 = map.lowerKey(right); // same, we don't care about the range starting at right
48

49
    // do this first, in case l1 == l2, the later one will change r1(or r2 in this case)
50
    if (l2 != null && map.get(l2) > right) {
51
      map.put(right, map.get(l2));
52
    }
53

54
    if (l1 != null && map.get(l1) > left) {
55
      map.put(l1, left);
56
    }
57

58
    // range that starts at left should be removed, so left is inclusive
59
    // range that starts at right should be kept, so right is exclusive
60
    map.subMap(left, true, right, false).clear();
61
  }
62
}