Оптимальный алгоритм перекрытия изображений

Question

Я хочу алгоритм со сложностью меньше O (n^2) для следующей задачи.

Существует N количество изображений одинаковой высоты, но различной ширины, которые перекрывают друг друга. Вам будут предоставлены начальная и конечная координаты вдоль оси x для всех изображений. Вы должны сказать, сколько изображений видно сверху. Поскольку высоты одинаковы, вам не нужно рассматривать что-либо о высоте или чем-либо по оси Y.

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

Порядок ввода данных будет представлять собой z-порядок. 1-й снимок будет в нижнем положении, а второй снимок будет на 1-м снимке, 3-е изображение будет на 2-ом снимке и т. Д. (Вы можете подумать о вертикальном стеке, где изображения выталкиваются один за другим)

Answer 1

Вот алгоритм O (n log n). Идея состоит в том, что мы представляем каждую картину как пару переходов, одну на своем левом краю и одну на своем правом краю, причем каждый переход, состоящий из пары (i, x), должен интерпретироваться как «При перемещении слева направо , изображение i становится видимым при x ". Мы добавляем изображения по одному в нижнем верхнем порядке Z, создавая список этих переходов, который описывает текущее состояние по мере продвижения. В этом списке хранятся только «активные» переходы, т. Е. Переходы, которые не затенены каким-то более высоким изображением. Это означает, что наряду с добавлением двух новых переходов для изображения, которое мы добавляем в настоящее время, нам нужно удалить все переходы, которые его покрывают. Мы сохраняем список активных переходов в самобалансирующемся двоичном дереве, которое хранит его по координате x и позволяет вставлять и удалять в O (log n) время.

Назовем координаты x левого и правого краев изображения i (i) и R (i) соответственно. Для перехода t = (i, x) мы напишем pic (t), чтобы извлечь индекс изображения i и pos (t), чтобы извлечь координату x x. Мы также хотим иметь возможность находить в списке (концептуально это список, хотя он хранится как двоичное дерево для эффективного поиска) активных переходов, самый правый активный переход, который происходит слева или слева от какого-либо заданного координата x: вызов this prec (x). Это можно найти в O (log n) времени. Наконец, учитывая переход t, мы хотим найти следующий переход в егоправо: назовите это succ (t). Это можно также извлечь в O (log n) времени (и фактически в амортизированном времени O (1)).

Чтобы избежать углового случая, мы прежде всего представляем себе, что на дне есть «фоновое» изображение, левая и правая координаты которого являются отрицательными и положительными бесконечностями соответственно. Мы присваиваем этот индекс изображения -1. Все остальные изображения индексируются по их позициям в порядке Z (т. Е. В порядке ввода).

Первоначально дерево активных переходов будет состоять только из фонового изображения, которое мы можем представить с использованием переходов (-1, -inf) и (-1, inf). (Не имеет значения, что «конечный» переход «возвращается к самому себе», -1 - все, о чем мы заботимся, это убедиться, что succ (t) всегда будет возвращать значение для любого нефонического изображения.) Затем, для каждого изображения i в свою очередь:

1. Посмотрите на запрос (L (i)). Пусть этот переход равен t = (j, y). (prec (L (i)) должен возвращать значение, так как фоновое изображение имеет начальный переход при -inf.)
2. Установить v = t.
3. Если pos (y) < L (i), то установите t = succ (t).
4. В то время как pos (t) < = R (i):
   • Установить u = succ (t).
   • Если pos (t) < R (i), то установите v = t.
   • Удалить t из списка активных переходов (время O (log n)).
   • Установить t = u. (u является лишь временной переменной для сохранения следующего значения t.)
5. Вставьте (i, L (i)) в список активных переходов, чтобы представить начало диапазона видимости изображения i.
6. Предыдущий внутренний цикл оставил v в последнем активном переходе (самый правый) с координатой x < R (i). Изображение, показанное этим переходом, станет видимым в pos (v), это изображение, которое возобновится, когда оно будет видимым, когда диапазон изображения i заканчивается на R (i), поэтому вставьте (pic (v), R (i)) в активный переход чтобы отразить это.

Этапы 3 и 4 удаляют любые перекрывающиеся переходы. Хотя может показаться, что этот внутренний цикл может привести к квадратичному времени, это не так, потому что любой вставленный переход будет удаляться этим внутренним циклом не более по всему алгоритму. Только 2n-переходы когда-либо вставлены, поэтому не более 2n-переходов могут быть удалены этим внутренним циклом во всех итерациях внешнего цикла.

К настоящему времени у нас будет активный список переходов с не более чем 2n переходами, который описывает видимость всех изображений. Сделайте проход с линейным временем слева направо над этим списком, установив флаг, видимый [i] для каждого перехода (i, x), который он содержит. Наконец, подсчитайте количество снимков, на которых установлены их видимые флаги: это ответ. (Для этого нужны отдельные шаги, потому что изображение может стать видимым много раз, если на нем есть много более узких изображений.)