В пространстве, где известны определенные занятые области, как я могу увидеть, не занята ли данная область?

#javascript

Вопрос:

Допустим, у меня есть пространство в диапазоне от 0 до 100, и вдоль этого пространства заняты определенные области. Скажем, 20-30 и 50-70.

Теперь предположим, что кто-то приходит и хочет заполнить пробелы 80-90. Как мне лучше всего проверить, не заняты ли эти пространства?

Я мог бы хранить свободное пространство во вложенных массивах (что я сейчас и делаю):

[[0, 19], [31, 49], [71, 100]

и цикл, если оператор проверяет, поместится ли 80-90 в любое из этих свободных пространств. Это кажется очень неэффективным. В худшем случае я мог бы говорить о тысячах элементов для перебора.

Я мог бы также использовать массив длиной 100 элементов с информацией о том, свободен ли каждый номер:

(100) 0: "free" 1: "free" 2: "free" 3: "free" 4: "free" ...

Таким образом, мне не пришлось бы перебирать несколько элементов, а можно было бы просто запустить оператор if для элементов 80-90 и посмотреть, возвращаются ли они свободными. С другой стороны, это означало бы заполнение и хранение массива миллиардами (100 — это просто пример, мой вариант использования включает около 1 миллиарда) элементов, просто чтобы найти свободное место.

Как можно было бы сделать это лучше? Или я должен использовать эти методы, которые я описал?

Редактировать: я использую 0-100 в качестве примера. В моем случае использования число фактически составляет около 1 миллиарда.

1. Числа не складываются, если у вас есть пробелы от 0 до 100, тогда зачем вам перебирать тысячи элементов или нужен массив с миллионами элементов?

2. @GuyIncognito, пример предназначен только для 100 элементов, а не для миллионов …

3. Ах. Извините. Я должен уточнить, что 100 был только примером для объяснения ситуации. На самом деле их число будет около 1 миллиарда.

4. @NinaScholz Да, вот почему «хранение массива с миллионами элементов» не имеет смысла. Сколько пробелов на самом деле? Уменьшение количества для примера не является необходимым и на самом деле вредно, потому что решение для 100 пробелов сильно отличается от решения для миллиарда пробелов.

5. @GuyIncognito Мои извинения… Я попытался отредактировать свой вопрос, чтобы уточнить.

Ответ №1:

Вы могли бы взять массив свободных диапазонов и выполнить двоичный поиск.

Это приведет к максимальной итерации 20 при наличии миллиона элементов.

 2 ** 20 === 1048576

1. Спасибо, я несколько новичок в этом и не смог придумать более сложных решений, чем приведенные. Бинарный поиск кажется хорошим способом. Мне нужно будет изучить ее реализацию.