Editorial for DMOPC '14 Contest 6 P4 - Bus Jam


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Phoenix1369

A greedy algorithm will find the optimal number of breaks each bus is required to take. For each bus in the list B sorted in descending order, calculate the difference between the estimated arrival times of the current B[i] and the next B[i + 1] bus. Then, if this difference is greater than the desired headway H, we can adjust the time accordingly by adding the appropriate length of time in breaks of length M, rounding up.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.