В этой задаче было достаточно для каждого пассажира перебрать место и за $$$\mathcal{O}(n)$$$ найти минимальное расстояние до уже занятого места. Для данных ограничений решения за $$$\mathcal{O}(n^3)$$$ было достаточно.