Алгоритм присвоения номера квартиры соседа снизу для нескольких квартир сразу

Question

[Дмитрий Сергеев]

Допустим есть дом, одна квартира на этаже, 9 этажей. Допустим что номер квартиры (N) будет так же являться ID квартиры и число это неизменное, тогда как номер квартиры может меняться, то есть

N | ID
9 | 9
8 | 8
7 | 7
6 | 6
5 | 5
4 | 4
3 | 3
2 | 2
1 | 1

Допустим нам нужно объединить несколько квартир в пары с соседями снизу и при этом сохранить правильность нумерации. Допустим для квартир с ID 3 и 5, получится

N | ID
7 | 9
6 | 8
5 | 7
4 | 6
3 | 5
3 | 4
2 | 3
2 | 2
1 | 1

Пока додумал одно решение:
1. находим номер квартиры снизу
2. обновляем номер квартиры выше
3. все номера квартир выше ID равно N = N-1
и так для каждого изменяемого ID

Может ещё кто-нибудь предложит более оптимальный алгоритм?

Comments

[Петруша Укропов]

А сколько квартир на этаже?

[Дмитрий Сергеев]

одна

Answer 1

[AM5800]

По приведенному вами примеру, можно видеть, что номер квартиры равен ID минус количество изменяемых ID, значение которых меньше или равно текущему.
Т.е.
N(2) = 2 — 0 = 2
N(3) = 3 — |{3}| = 2
N(4) = 4 — |{3}| = 3
N(5) = 5 — |{3, 5}| = 3

Т.е. для каждого запроса номера — сложность ответа будет O(m), где m — число изменяемых ID (можно и быстрее).
Если запросов много, то лучше обновить все сразу. Например так:
Перегенерируем все номера начиная с первого так, что номер очередной квартиры равен значению счетчика. Значение счетчика увеличивается на единицу только если текущий ID не равен одному из изменяемых. Иначе — счетчик не увеличивается.
Итоговая сложность — O(n) при условии, что принадлежность ID списку проверяется за O(1).

Честно говоря, очень долго пытался понять суть проблемы. Решение кажется слишком простым. Возможно, я что-то не правильно понял.

Answer 2

[Arktos]

Вместо массива можно использовать дерево отрезков. Тогда нахождение/обновление номера по id будет выполняться за O(log(n)), уменьшение всего хвоста на 1 за O(log(n)), нахождение id по номеру за O(log(n)^2) (посредством бинарного поиска). Можно вместо дерева отрезков использовать множество объединенных квартир — будет та же ассимптотика, но тогда множество должно поддерживать операцию «Сколько элементов левее данной»