715. Range Module
leetcode hard
Task
Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).
Пример:
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]
C# solution
matched/originalpublic class RangeModule {
private List<(int, int)> ranges;
public RangeModule() {
ranges = new List<(int, int)>();
}
public void AddRange(int left, int right) {
var newRanges = new List<(int, int)>();
int i = 0;
while (i < ranges.Count && ranges[i].Item2 < left) {
newRanges.Add(ranges[i]);
i++;
}
while (i < ranges.Count && ranges[i].Item1 <= right) {
left = Math.Min(left, ranges[i].Item1);
right = Math.Max(right, ranges[i].Item2);
i++;
}
newRanges.Add((left, right));
while (i < ranges.Count) {
newRanges.Add(ranges[i]);
i++;
}
ranges = newRanges;
}
public bool QueryRange(int left, int right) {
foreach (var range in ranges) {
if (range.Item1 <= left && right <= range.Item2) {
return true;
}
}
return false;
}
public void RemoveRange(int left, int right) {
var newRanges = new List<(int, int)>();
foreach (var range in ranges) {
if (range.Item1 < left) {
newRanges.Add((range.Item1, Math.Min(range.Item2, left)));
}
if (right < range.Item2) {
newRanges.Add((Math.Max(range.Item1, right), range.Item2)));
}
}
ranges = newRanges;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class RangeModule {
private List<(int, int)> ranges;
public RangeModule() {
ranges = new List<(int, int)>();
}
public void AddRange(int left, int right) {
var newRanges = new List<(int, int)>();
int i = 0;
while (i < ranges.size() && ranges[i].Item2 < left) {
newRanges.push_back(ranges[i]);
i++;
}
while (i < ranges.size() && ranges[i].Item1 <= right) {
left = min(left, ranges[i].Item1);
right = max(right, ranges[i].Item2);
i++;
}
newRanges.push_back((left, right));
while (i < ranges.size()) {
newRanges.push_back(ranges[i]);
i++;
}
ranges = newRanges;
}
public bool QueryRange(int left, int right) {
foreach (var range in ranges) {
if (range.Item1 <= left && right <= range.Item2) {
return true;
}
}
return false;
}
public void RemoveRange(int left, int right) {
var newRanges = new List<(int, int)>();
foreach (var range in ranges) {
if (range.Item1 < left) {
newRanges.push_back((range.Item1, min(range.Item2, left)));
}
if (right < range.Item2) {
newRanges.push_back((max(range.Item1, right), range.Item2)));
}
}
ranges = newRanges;
}
}Java solution
matched/originalimport java.util.ArrayList;
import java.util.List;
public class RangeModule {
private List<int[]> ranges;
public RangeModule() {
ranges = new ArrayList<>();
}
public void addRange(int left, int right) {
List<int[]> newRanges = new ArrayList<>();
int i = 0;
while (i < ranges.size() && ranges.get(i)[1] < left) {
newRanges.add(ranges.get(i));
i++;
}
while (i < ranges.size() && ranges.get(i)[0] <= right) {
left = Math.min(left, ranges.get(i)[0]);
right = Math.max(right, ranges.get(i)[1]);
i++;
}
newRanges.add(new int[] {left, right});
while (i < ranges.size()) {
newRanges.add(ranges.get(i));
i++;
}
ranges = newRanges;
}
public boolean queryRange(int left, int right) {
for (int[] range : ranges) {
if (range[0] <= left && right <= range[1]) {
return true;
}
}
return false;
}
public void removeRange(int left, int right) {
List<int[]> newRanges = new ArrayList<>();
for (int[] range : ranges) {
if (range[0] < left) {
newRanges.add(new int[] {range[0], Math.min(range[1], left)});
}
if (right < range[1]) {
newRanges.add(new int[] {Math.max(range[0], right), range[1]});
}
}
ranges = newRanges;
}
}Python solution
matched/originalclass RangeModule:
def __init__(self):
self.ranges = []
def addRange(self, left, right):
new_ranges = []
i = 0
while i < len(self.ranges) and self.ranges[i][1] < left:
new_ranges.append(self.ranges[i])
i += 1
while i < len(self.ranges) and self.ranges[i][0] <= right:
left = min(left, self.ranges[i][0])
right = max(right, self.ranges[i][1])
i += 1
new_ranges.append((left, right))
while i < len(self.ranges):
new_ranges.append(self.ranges[i])
i += 1
self.ranges = new_ranges
def queryRange(self, left, right):
for l, r in self.ranges:
if l <= left and right <= r:
return True
return False
def removeRange(self, left, right):
new_ranges = []
for l, r in self.ranges:
if l < left:
new_ranges.append((l, min(r, left)))
if right < r:
new_ranges.append((max(l, right), r))
self.ranges = new_rangesExplanation
Algorithm
Инициализируйте класс RangeModule с пустым списком диапазонов.
Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.
Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.
😎