[Leetcode] Problem 715 - Range Module

Posted on | In ,

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

  • addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
  • queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
  • removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Note

  • A half open interval [left, right) denotes all real numbers left <= x < right.
  • 0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
  • The total number of calls to addRange in a single test case is at most 1000.
  • The total number of calls to queryRange in a single test case is at most 5000.
  • The total number of calls to removeRange in a single test case is at most 1000.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private TreeMap<Integer, Integer> interval;

public RangeModule() {
    interval = new TreeMap<>();
}

public void addRange(int left, int right) {
    Integer leftFloor = interval.floorKey(left);
    Integer rightFloor = interval.floorKey(right);
    left = (leftFloor != null && interval.get(leftFloor) >= left) ? leftFloor : left;
    right = (rightFloor != null && interval.get(rightFloor) > right) ? interval.get(rightFloor) : right;

    interval.put(left, right);
    interval.subMap(left, false, right, true).clear();
}

public boolean queryRange(int left, int right) {
    Integer floor = interval.floorKey(left);
    return floor != null && interval.get(floor) >= right;
}

public void removeRange(int left, int right) {
    Integer leftFloor = interval.floorKey(left);
    Integer rightFloor = interval.floorKey(right);

    if (rightFloor != null && interval.get(rightFloor) > right)
        interval.put(right, interval.get(rightFloor));
    if (leftFloor != null && interval.get(leftFloor) > left)
        interval.put(leftFloor, left);

    interval.subMap(left, true, right, false).clear();
}