Данный набор интервалов отсортирован по времени начала.Посчитайте все интервалы, в которых есть время "T" в O (logn)

Question

Предположим, что список интервалов может быть [[1,3], [2,4], [6,12]] и время запроса T = 3. Число интервалов, которые имеют 3 в приведенном выше списке, равно 2(то есть) [[1,3], [2,4]].Можно ли это сделать за время O (logn)?

Answer 1

Давайте предположим, что интервалы отсортированы по времени начала.Бинарный поиск O (log n) исключит интервалы, которые не могут содержать T .Оставшиеся могут .

Предполагается, что время окончания также не отсортировано (OP)

Вам нужно отсканировать оставшиеся, O (n) считая их.Общая сложность O (n) .Учитывая это, вы, возможно, также никогда не выполняли двоичный поиск и просто просматривали весь список.

Предполагая, что время окончания также сортируется

Если оставшиеся также отсортированы по времени окончания, вы можетевыполните еще один бинарный поиск, сохраняя сложность на O (log n) .

Но вы еще не закончили.Вам нужен счет.

Вы знаете, с чего начать.Если бы вы не сделали, вы не могли бы бинарный поиск.Вы будете знать индексы последних тестов каждого бинарного поиска.Отсюда это опция вычисления O (1) .

Таким образом, общая сложность составляет O (log n) для этой опции.

Answer 2

В общем случае это невозможно сделать за время O (log n).

Вы можете выполнить двоичный поиск по времени начала, чтобы найти последний интервал, который может содержать время запроса, но посколькуподразумеваемое упорядочение по времени окончания, вы последовательно выполняете поиск от начала списка до элемента, который вы определили как последний, чтобы определить, относится ли время запроса к какому-либо из этих интервалов.

Рассмотрим, например, [(1,7),(2,11),(3,8),(4,5),(6,10),(7,9)], со временем запроса 7.

Бинарный поиск по времени начала скажет вам, что все интервалы могут содержать время запроса.Но поскольку время окончания не в каком-то определенном порядке, вы не можете выполнить бинарный поиск по ним.Вы должны смотреть на каждый отдельный интервал, чтобы определить, больше или равно время окончания времени запроса.Здесь вы видите, что (4,5) не содержит время запроса.

Answer 3

Хорошо, стоит отметить, что для интервала, содержащего T, его время начала должно быть меньше или равно T. Поскольку они отсортированы по времени начала, вы можете использовать простой двоичный поиск, чтобы исключить всекоторые начинаются слишком поздно во время O (log n).

Если мы можем предположить, что они также отсортированы по времени окончания - то есть, ни один интервал не полностью охватывает предыдущий интервал - тогда вы можете использовать другой двоичный файлищите, чтобы исключить все те, чьи конечные времена находятся перед T. Это сохранит время выполнения в O (log n).

Если мы не можем сделать это предположение, все усложняется, и я могу 'Не думайте о каком-либо способе добиться большего успеха, чем O (n log n) [путем сортировки оставшегося списка по времени окончания и выполнения другого двоичного поиска по этому вопросу].Возможно, есть способ?

РЕДАКТИРОВАТЬ Как говорит Qbyte ниже, окончательная сортировка является излишней;Вы можете получить его до O (n) с помощью простого линейного поиска по оставшемуся множеству.С другой стороны, если вы все равно собираетесь использовать решение O (n), вы можете также пропустить весь алгоритм и просто выполнить линейный поиск по исходному набору.