Algorithm
Problem Name: 715. Range Module
A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.
A half-open interval [left, right)
denotes all the real numbers x
where left <= x < right
.
Implement the RangeModule
class:
RangeModule()
Initializes the object of the data structure.void 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.boolean queryRange(int left, int right)
Returnstrue
if every real number in the interval[left, right)
is currently being tracked, andfalse
otherwise.void removeRange(int left, int right)
Stops tracking every real number currently being tracked in the half-open interval[left, right)
.
Example 1:
Input ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]] Output [null, null, null, true, false, true] Explanation RangeModule rangeModule = new RangeModule(); rangeModule.addRange(10, 20); rangeModule.removeRange(14, 16); rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked) rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked) rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
Constraints:
1 <= left < right <= 109
- At most
104
calls will be made toaddRange
,queryRange
, andremoveRange
.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const RangeModule = function() {
this.range = []
}
RangeModule.prototype.addRange = function(left, right) {
let index1 = this.range.length
let low = 0
let high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid][1] >= left) {
index1 = Math.min(index1, mid)
high = mid - 1
} else {
low = mid + 1
}
}
let index2 = -1
low = 0
high = this.range.length - 1
while (low < = high) {
const mid = (low + high) >> 1
if (this.range[mid][0] < = right) {
index2 = Math.max(index2, mid)
low = mid + 1
} else {
high = mid - 1
}
}
if (index1 === this.range.length) {
this.range.push([left, right])
return
} else if (index2 === -1) {
this.range.unshift([left, right])
return
}
left = Math.min(left, this.range[index1][0])
right = Math.max(right, this.range[index2][1])
this.range.splice(index1, index2 - index1 + 1, [left, right])
}
RangeModule.prototype.queryRange = function(left, right) {
let index = -1
let low = 0
let high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid][0] < = left) {
index = Math.max(index, mid)
low = mid + 1
} else {
high = mid - 1
}
}
if (index === -1 || this.range[index][1] < right) {
return false
}
return true
}
RangeModule.prototype.removeRange = function(left, right) {
let index1 = this.range.length
let low = 0
let high = this.range.length - 1
while (low <= high) {
const mid = (low + high) >> 1
if (this.range[mid][1] >= left) {
index1 = Math.min(index1, mid)
high = mid - 1
} else {
low = mid + 1
}
}
let index2 = -1
low = 0
high = this.range.length - 1
while (low < = high) {
const mid = (low + high) >> 1
if (this.range[mid][0] <= right) {
index2 = Math.max(index2, mid)
low = mid + 1
} else {
high = mid - 1
}
}
if (index1 === this.range.length || index2 === -1) {
return
}
const newRange = []
if (left > this.range[index1][0]) {
newRange.push([this.range[index1][0], left])
}
if (right < this.range[index2][1]) {
newRange.push([right, this.range[index2][1]])
}
this.range.splice(index1, index2 - index1 + 1, ...newRange)
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
from bisect import bisect_left as bl, bisect_right as br
class RangeModule:
def __init__(self):
self._X = []
def addRange(self, left, right):
i, j = bl(self._X, left), br(self._X, right)
self._X[i:j] = [left]*(i%2 == 0) + [right]*(j%2 == 0)
def queryRange(self, left, right):
i, j = br(self._X, left), bl(self._X, right)
return i == j and i%2 == 1
def removeRange(self, left, right):
i, j = bl(self._X, left), br(self._X, right)
self._X[i:j] = [left]*(i%2 == 1) + [right]*(j%2 == 1)
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0715_RangeModule
{
private readonly SortedList < int, int> list;
public _0715_RangeModule()
{
list = new SortedList<int, int>();
}
public void AddRange(int left, int right)
{
var leftIndex = GetIndex(left);
if (leftIndex >= 0) left = list.Keys[leftIndex];
else leftIndex = ~leftIndex;
var rightIndex = GetIndex(right);
if (rightIndex >= 0) right = list.Values[rightIndex];
else rightIndex = ~rightIndex - 1;
for (int i = leftIndex; i < = rightIndex; i++)
list.RemoveAt(leftIndex);
list[left] = right;
}
public bool QueryRange(int left, int right)
{
var leftIndex = GetIndex(left);
var rightIndex = GetIndex(right);
return leftIndex == rightIndex && leftIndex >= 0;
}
public void RemoveRange(int left, int right)
{
var leftIndex = GetIndex(left);
var rightIndex = GetIndex(right);
if (rightIndex >= 0)
list[right] = list.Values[rightIndex];
else
rightIndex = ~rightIndex - 1;
if (leftIndex >= 0)
{
list[list.Keys[leftIndex]] = left;
leftIndex++;
}
else
leftIndex = ~leftIndex;
for (int i = leftIndex; i < = rightIndex; i++)
list.RemoveAt(leftIndex);
}
private int GetIndex(int value)
{
var index = Array.BinarySearch(list.Keys.ToArray(), value);
if (index >= 0) return index;
index = ~index;
if (index > 0 && list.Values[index - 1] >= value)
return index - 1;
else
return ~index;
}
}
}
Copy The Code &
Try With Live Editor
Input
Output