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

Допустим есть дом, одна квартира на этаже, 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

Может ещё кто-нибудь предложит более оптимальный алгоритм?
  • Вопрос задан
  • 3044 просмотра
Пригласить эксперта
Ответы на вопрос 2
@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).

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы