Вычисление наименьшего положительного целого, не охватываемого никаким набором интервалов

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

Сам вопрос был довольно интересным, и я думал об этом неделю, не найдя удовлетворительного решения. Надеюсь, кто-то может помочь?

Вопрос заключается в следующем: задает список из N целых интервалов, границы которых могут принимать любые значения от 0 до N³, найти наименьшее целое число i такое, что i не принадлежит на любой из входных интервалов.

Например, если задан список [3,5] [2,8] [0,3] [10,13] (N = 4), алгоритм должен возвращать 9.

Самое простое решение, о котором я могу думать, работает в O(n log(n)) и состоит из трех шагов:

Сортировка интервалов путем увеличения нижней границы
- Если наименьшая нижняя границa > 0, верните 0;
- В противном случае повторно слияние первого интервала со вторым, пока первый интервал (скажем [a, b]) не коснется второго (скажем [c, d]) - то есть до тех пор, пока b + 1 < c, или пока не будет только один интервал.
Возврат b + 1

Это простое решение работает в O(n log(n)), но исходный плакат написал, что алгоритм должен работать в O(n).. Это тривиально, если интервалы уже отсортированы, но пример, который дал OP включая несортированные интервалы. Я предполагаю, что это должно иметь какое-то отношение к N³ bound, но я не уверен, что... Хеширование? Линейная сортировка времени? Идеи приветствуются.

Ниже приведена грубая реализация python для алгоритма, описанного выше:

def merge(first, second):
    (a, b), (c, d) = first, second
    if c <= b + 1:
        return (a, max(b, d))
    else:
        return False

def smallest_available_integer(intervals):
    # Sort in reverse order so that push/pop operations are fast
    intervals.sort(reverse = True)

    if (intervals == [] or intervals[-1][0] > 0):
        return 0

    while len(intervals) > 1:
        first = intervals.pop()
        second = intervals.pop()

        merged = merge(first, second)
        if merged:
            print("Merged", first, "with", second, " -> ", merged)
            intervals.append(merged)
        else:
            print(first, "cannot be merged with", second)
            return first[1] + 1

print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)]))

Вывод:

Merged (0, 3) with (2, 8)  ->  (0, 8)
Merged (0, 8) with (3, 5)  ->  (0, 8)
(0, 8) cannot be merged with (10, 13)
9

Ответ 1

Разрабатывая комментарий @mrip: вы можете сделать это в O (n) раз, используя точный алгоритм, который вы описали, но изменяете, как работает алгоритм сортировки.

Обычно сортировка radix использует базу 2: элементы делятся на два разных ведра на основе того, являются ли их биты 0 или 1. Каждый раунд сортировки radix занимает время O (n), и есть один раунд на бит наибольшее число. Вызвав этого самого большого n-го U, это означает, что временная сложность O (n log U).

Однако вы можете изменить базу сортировки radix на другие базы. Используя базу b, каждый раунд занимает время O (n + b), так как для инициализации и итерации по ведрам и времени O (n) требуется время O (b) для распределения элементов в ведрах. Затем используются лог _b U раундов. Это дает время выполнения O ((n + b) log _b U).

Трюк здесь заключается в том, что, поскольку максимальное число U = n ³ вы можете установить b = n и использовать базовую сортировку base-n. Число раундов теперь log _n U = log _n n ³= 3, и каждый раунд принимает O (n) время, поэтому общее число работа по сортировке чисел равна O (n). В более общем плане вы можете сортировать числа в диапазоне [0, n ^k) за время O (kn) для любого k. Если k - фиксированная константа, это O (n) время.

В сочетании с вашим исходным алгоритмом это решает проблему во времени O (n).

Надеюсь, это поможет!

Ответ 2

Еще одна идея - это как-то использовать дополнение этих интервалов. Предположим, что C() дает вам дополнение для интервала, например C ([3,5]) будет целым числом меньше 3 и числом больше 5. Если максимальное число равно N ^ 3, то с использованием по модулю N ^ 3 + 1 вы могли бы представить это как еще один интервал [6, (N ^ 3 + 1) +2].

Если вам нужно число, которое не принадлежит ни одному из первоначальных интервалов, этот же номер должен присутствовать во всех дополнениях этих интервалов. Затем оно сводится к написанию функции, которая может рассчитать пересечение любых двух таких "интервалов комплемента".

Я не реализовал эту идею, так как мои рисунки на ручке и бумаге указывали на то, что при расчете такого пересечения было больше случаев, чем я себе представлял. Но я думаю, что эта идея верна, и это приведет к алгоритму O (n).

ИЗМЕНИТЬ

С другой стороны, существует худший сценарий, который делает вещи более сложными, чем я предполагал.