Задача: 715. Range Module
Сложность: hard

Модуль 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]

👨‍💻 Алгоритм:

1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.

2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.

3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.

😎 Решение:

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.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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний