Структура данных для эффективного распределения

Question

Предположим, у меня есть поезд с N вагонами. Каждый вагон i имеет ячейки n_i, в то время как каждая ячейка имеет 6 мест.

Предположим, что 0 < x < = 6 пассажиров ввели вагон i нашего поезда и захотите сесть в ту же камеру. Я хочу найти первую подходящую ячейку, у которой достаточно свободных мест в худшем случае O(log*n).

Инициализация системы может занимать до O(n).

n = общее количество ячеек в поезде.

Я попытался решить эту проблему с помощью непересекающихся наборов 6 * (количество вагонов), однако у меня возникли трудности с поддержанием такого сложного решения.

PS: log*n - Итерированный логарифм.

Answer 1

Надеясь, что это не было непреднамеренное упущение, мое решение дает новоприбывшим пассажирам небольшую прогулку по вагонам поезда. В описании проблемы не было написано, что в конце концов они найдут свои места в фургоне, в который они вошли. И сложность, с которой сталкиваются пассажиры, не вносит вклад в сложность алгоритма;)

Достаточно использовать следующий тип данных вместе с тем, как организованы данные. Член индекса - это так, что мы также можем отслеживать ячейки, когда они перемещаются по структуре данных по прибытии новых пассажиров. тип Cell также может быть просто int (идентификатор вагона, который также является информационным).

type Cell = { Index : int; Wagon : int } 

Теперь мы сформулируем нашу проблему в терминах массива списков. Размер массива равен 7 (0..6 вакансий в ячейках).

Начнем с пустого поезда. Таким образом, все ячейки находятся в списке, хранящихся в массиве index 6 (6 вакансий = пустая ячейка).

По прибытии x пассажиров с x в [1..6] все, что нам нужно сделать, это проверить массив [x] на массив [6] за то, что он не пуст. Первый непустой список содержит ячейку, в которую мы хотим набивать наших пассажиров.

С тех пор вакансии в этой ячейке - старыеVacancies (индекс массива) - x, мы добавляем ячейку в список в массиве [oldVacancies - x ].

Этот алгоритм должен соответствовать требованиям сложности вопроса ... по крайней мере.

Здесь пример реализации в F #:

module Trains = 
    type Cell = { Index : int; Wagon : int } 
    type Problem = List<Cell> [] 

    let init ncells cellsPerWagon = 
     let initCells = 
      [ for i in 0..(ncells-1) do yield { Index = i; Wagon = i % cellsPerWagon } ] 
     Array.init 7 (fun i -> if i = 6 then initCells else []) 

    let arrival (nPassengers : int) (problem : Problem) : Problem option = 
     let rec findCell (index : int) : (Cell * int) option = 
      if index > 6 then None 
      else 
       match problem.[index] with 
       | [] -> findCell (index+1) 
       | c::cs -> 
        problem.[index] <- cs 
        Some(c,index) 
     match nPassengers with 
     | 0 -> Some(problem) 
     | x when x > 6 -> None 
     | _ -> 
      let maybeFound = findCell nPassengers 
      match maybeFound with 
      | Some(cell,vacancies) -> 
       problem.[vacancies - nPassengers] <- cell :: problem.[vacancies - nPassengers] 
       Some(problem) 
      | None -> None