Formatted question description: https://leetcode.ca/all/715.html

# 715. Range Module

Hard

## Description

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 1:

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.

## Solution

Create a class Interval that represents intervals. Each object of Interval has data fields start and end that represents the start position and the end position. The intervals are compared according to start in ascending order and then according to end in ascending order.

In the class, maintain a tree set to store the intervals, where the intervals are sorted in ascending order.

For method addRange(int left, int right), loop over all the intervals in the tree set. If an interval has intersection with the new interval [left, right) (which means the two intervals can be merged into a new interval), then update left and right to a larger interval, and remove the current interval from the tree set. If the current interval’s start is greater than right, then break the loop. Add the new interval [left, right) (where the two values may be updated) to the tree set.

For method queryRange(int left, int right), find the previous interval of the current interval [left, right) using floor method. If the previous interval exists and it contains the current interval, return true. Otherwise, find the next interval of the current interval using ceiling method. If the next interval exists and it contains the current interval, return true. Otherwise, return false.

For method removeRange(int left, int right), loop over all the intervals in the tree set. If an interval has intersection with the removed interval [left, right) (which means the two intervals can be merged into a new interval), then remove the current interval from the tree set, and if there are existing intervals after removing the current interval, add the existing intervals to the tree set.

• class RangeModule {
TreeSet<Interval> set;

public RangeModule() {
set = new TreeSet<Interval>();
}

public void addRange(int left, int right) {
TreeSet<Interval> prevSet = new TreeSet<Interval>(set);
for (Interval interval : prevSet) {
if (interval.end >= left && interval.start <= right) {
left = Math.min(left, interval.start);
right = Math.max(right, interval.end);
set.remove(interval);
} else if (interval.start > right)
break;
}
}

public boolean queryRange(int left, int right) {
Interval curr = new Interval(left, right);
Interval prev = set.floor(curr);
if (prev != null && prev.end >= right)
return true;
else {
Interval next = set.ceiling(curr);
if (next != null && next.start == left)
return true;
else
return false;
}
}

public void removeRange(int left, int right) {
TreeSet<Interval> prevSet = new TreeSet<Interval>(set);
for (Interval interval : prevSet) {
if (interval.end >= left && interval.start <= right) {
set.remove(interval);
if (interval.start < left)
if (interval.end > right)
} else if (interval.start > right)
break;
}
}
}

class Interval implements Comparable<Interval> {
int start;
int end;

public Interval(int start, int end) {
this.start = start;
this.end = end;
}

public int compareTo(Interval interval2) {
if (this.start != interval2.start)
return this.start - interval2.start;
else
return this.end - interval2.end;
}

public boolean equals(Object obj) {
if (obj instanceof Interval) {
Interval interval2 = (Interval) obj;
return this.start == interval2.start && this.end == interval2.end;
} else
return false;
}
}

/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule obj = new RangeModule();
* boolean param_2 = obj.queryRange(left,right);
* obj.removeRange(left,right);
*/

• // OJ: https://leetcode.com/problems/range-module/
// Time:
//      RangeModule: O(1)
//      queryRange: O(logN)
//      removeRange: O(N)
// Space: O(N)
class RangeModule {
map<int, int> m;
public:
RangeModule() {}
void addRange(int left, int right) {
auto it = m.lower_bound(left);
if (it != begin(m) && prev(it)->second >= left) --it;
if (it != end(m)) left = min(left, it->first);
while (it != end(m) && it->first <= right) {
if (it->second <= right) it = m.erase(it);
else {
right = it->second;
it = m.erase(it);
right = it->second;
break;
}
}
m[left] = right;
}
bool queryRange(int left, int right) {
auto it = m.lower_bound(left);
if (it != begin(m) && prev(it)->second > left) --it;
if (it == end(m)) return false;
return it->first <= left && it->second >= right;
}
void removeRange(int left, int right) {
auto it = m.lower_bound(left);
if (it != begin(m) && prev(it)->second > left) {
--it;
int r = it->second;
it->second = left;
if (right < r) {
m[right] = r;
return;
}
++it;
}
while (it != end(m) && it->first < right) {
if (it->second <= right) it = m.erase(it);
else {
int r = it->second;
m.erase(it);
m[right] = r;
break;
}
}
}
};

• print("Todo!")