История изменений
Исправление den73, (текущая версия) :
за O(1) находим сегмент дороги и потом линейным поиском в массиве
Неправда, в общем случае ты не найдёшь его за O(1). Т.к. никто не сказал, что id-ы машин будут от 0 до N. Машины будут появляться и исчезать, поэтому могут возникнуть дыры в id-ах. Либо возникнет утечка памяти, либо понадобится отслеживание дыр, либо нахождение сегмента дороги по машине потребует обращения к чему-то вроде хеш-таблицы или B-дерева.
Если же id-ы машин будут от 0 до N, то я точно так же буду искать их через массив, как и ты.
Исходная версия den73, :
за O(1) находим сегмент дороги и потом линейным поиском в массиве
Неправда, в общем случае ты не найдёшь его за O(1). Т.к. никто не сказал, что id-ы машин будут от 0 до N. Машины будут появляться и исчезать, поэтому могут возникнуть дыры в id-ах. Либо возникнет утечка памяти, либо понадобится отслеживание дыр, либо нахождение сегмента дороги по машине потребует обращения к чему-то вроде хеш-таблицы или B-дерева.