The Range Module problem requires you to design a data structure that efficiently tracks ranges of numbers (intervals) and supports three main operations:
addRange(left, right): Adds the half-open interval [left, right) to the structure. This means all numbers from left (inclusive) up to right (exclusive) are now tracked.queryRange(left, right): Returns true if every number in the interval [left, right) is currently being tracked by the structure, and false otherwise.removeRange(left, right): Stops tracking every number in the interval [left, right).The intervals can overlap, and the structure must automatically merge or split intervals as needed. The input numbers can be very large, so efficiency is key. There is no restriction on how many times the operations are called.
At first glance, it might seem reasonable to store every individual number being tracked. However, this would be extremely inefficient, especially if the ranges are large. Instead, we should focus on storing the intervals themselves in a way that makes it easy to add, query, and remove ranges.
One way to do this is to keep a sorted list of non-overlapping intervals. When adding or removing a range, we merge or split intervals as needed. For queries, we check if the entire query interval is covered by existing intervals.
The main challenge is efficiently updating and querying these intervals, especially when there are many overlapping or adjacent intervals. Using a balanced search structure (like SortedList in Python, TreeMap in Java, or std::set in C++) helps us achieve fast lookups and updates.
We will maintain a sorted list (or set) of non-overlapping intervals, where each interval is represented as a pair [start, end).
This approach ensures that the interval list is always sorted and non-overlapping, allowing efficient updates and queries.
Let's walk through an example:
addRange(10, 20)
[][10, 20): [[10, 20)]addRange(15, 25)
[[10, 20)][10, 20). Merge to [10, 25)[[10, 25)]removeRange(14, 16)
[[10, 25)][10, 25). Split into [10, 14) and [16, 25)[[10, 14), [16, 25)]queryRange(10, 14)
[10, 14) is fully covered.true.queryRange(13, 15)
[13, 14) is covered, but [14, 15) is not.false.O(N) space and O(1) for each update/query, but N can be huge.M be the number of intervals stored.O(\log M) time using binary search or balanced trees, plus up to O(M) in the worst case for merging or splitting, though typically much less.O(M), where M is the number of non-overlapping intervals.M is kept relatively small.
The Range Module problem is best solved by maintaining a sorted list of non-overlapping intervals, merging and splitting as needed when adding or removing ranges. This approach is both efficient and elegant, allowing for fast updates and queries without explicitly storing every number. The key insight is to always keep the interval list minimal and sorted, which makes all operations straightforward and efficient.
import bisect
class RangeModule:
def __init__(self):
self.intervals = []
def addRange(self, left: int, right: int) -> None:
new_intervals = []
placed = False
for start, end in self.intervals:
if end < left:
new_intervals.append([start, end])
elif right < start:
if not placed:
new_intervals.append([left, right])
placed = True
new_intervals.append([start, end])
else:
left = min(left, start)
right = max(right, end)
if not placed:
new_intervals.append([left, right])
self.intervals = new_intervals
def queryRange(self, left: int, right: int) -> bool:
i = bisect.bisect_right(self.intervals, [left, float('inf')]) - 1
if i >= 0 and self.intervals[i][0] <= left and self.intervals[i][1] >= right:
return True
return False
def removeRange(self, left: int, right: int) -> None:
new_intervals = []
for start, end in self.intervals:
if end <= left or start >= right:
new_intervals.append([start, end])
else:
if start < left:
new_intervals.append([start, left])
if end > right:
new_intervals.append([right, end])
self.intervals = new_intervals
#include <vector>
#include <algorithm>
class RangeModule {
public:
std::vector<std::pair<int, int>> intervals;
RangeModule() {}
void addRange(int left, int right) {
std::vector<std::pair<int, int>> res;
bool placed = false;
for (auto &it : intervals) {
if (it.second < left) {
res.push_back(it);
} else if (right < it.first) {
if (!placed) {
res.push_back({left, right});
placed = true;
}
res.push_back(it);
} else {
left = std::min(left, it.first);
right = std::max(right, it.second);
}
}
if (!placed) {
res.push_back({left, right});
}
intervals = std::move(res);
}
bool queryRange(int left, int right) {
auto it = std::upper_bound(intervals.begin(), intervals.end(), std::make_pair(left, INT_MAX));
if (it == intervals.begin()) return false;
--it;
return it->first <= left && it->second >= right;
}
void removeRange(int left, int right) {
std::vector<std::pair<int, int>> res;
for (auto &it : intervals) {
if (it.second <= left || it.first >= right) {
res.push_back(it);
} else {
if (it.first < left) res.push_back({it.first, left});
if (it.second > right) res.push_back({right, it.second});
}
}
intervals = std::move(res);
}
};
import java.util.*;
class RangeModule {
private List<int[]> intervals;
public RangeModule() {
intervals = new ArrayList<>();
}
public void addRange(int left, int right) {
List<int[]> res = new ArrayList<>();
boolean placed = false;
for (int[] interval : intervals) {
if (interval[1] < left) {
res.add(interval);
} else if (right < interval[0]) {
if (!placed) {
res.add(new int[]{left, right});
placed = true;
}
res.add(interval);
} else {
left = Math.min(left, interval[0]);
right = Math.max(right, interval[1]);
}
}
if (!placed) {
res.add(new int[]{left, right});
}
intervals = res;
}
public boolean queryRange(int left, int right) {
int l = 0, r = intervals.size() - 1;
while (l <= r) {
int m = (l + r) / 2;
int[] interval = intervals.get(m);
if (interval[0] > left) {
r = m - 1;
} else if (interval[1] <= left) {
l = m + 1;
} else {
return interval[0] <= left && interval[1] >= right;
}
}
return false;
}
public void removeRange(int left, int right) {
List<int[]> res = new ArrayList<>();
for (int[] interval : intervals) {
if (interval[1] <= left || interval[0] >= right) {
res.add(interval);
} else {
if (interval[0] < left) res.add(new int[]{interval[0], left});
if (interval[1] > right) res.add(new int[]{right, interval[1]});
}
}
intervals = res;
}
}
class RangeModule {
constructor() {
this.intervals = [];
}
addRange(left, right) {
const res = [];
let placed = false;
for (const [start, end] of this.intervals) {
if (end < left) {
res.push([start, end]);
} else if (right < start) {
if (!placed) {
res.push([left, right]);
placed = true;
}
res.push([start, end]);
} else {
left = Math.min(left, start);
right = Math.max(right, end);
}
}
if (!placed) {
res.push([left, right]);
}
this.intervals = res;
}
queryRange(left, right) {
let l = 0, r = this.intervals.length - 1;
while (l <= r) {
const m = Math.floor((l + r) / 2);
const [start, end] = this.intervals[m];
if (start > left) {
r = m - 1;
} else if (end <= left) {
l = m + 1;
} else {
return start <= left && end >= right;
}
}
return false;
}
removeRange(left, right) {
const res = [];
for (const [start, end] of this.intervals) {
if (end <= left || start >= right) {
res.push([start, end]);
} else {
if (start < left) res.push([start, left]);
if (end > right) res.push([right, end]);
}
}
this.intervals = res;
}
}