Задача: 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) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части. 😎 Решение: class RangeModule { private val ranges = mutableListOf<Pair<Int, Int>>() fun addRange(left: Int, right: Int) { val newRanges = mutableListOf<Pair<Int, Int>>() var i = 0 while (i < ranges.size && ranges[i].second < left) { newRanges.add(ranges[i]) i++ } var l = left var r = right while (i < ranges.size && ranges[i].first <= right) { l = minOf(l, ranges[i].first) r = maxOf(r, ranges[i].second) i++ } newRanges.add(l to r) while (i < ranges.size) { newRanges.add(ranges[i]) i++ } ranges.clear() ranges.addAll(newRanges) } fun queryRange(left: Int, right: Int): Boolean { for (range in ranges) { if (range.first <= left && right <= range.second) { return true } } return false } fun removeRange(left: Int, right: Int) { val newRanges = mutableListOf<Pair<Int, Int>>() for (range in ranges) { if (range.first < left) { newRanges.add(range.first to minOf(range.second, left)) } if (right < range.second) { newRanges.add(maxOf(range.first, right) to range.second) } } ranges.clear() ranges.addAll(newRanges) } } Ставь 👍 и забирай 📚 Базу знаний