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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
A greedy algorithm will find the optimal number of breaks each bus is required to take. For each bus in the list sorted in descending order, calculate the difference between the estimated arrival times of the current and the next bus. Then, if this difference is greater than the desired headway , we can adjust the time accordingly by adding the appropriate length of time in breaks of length , rounding up.
Time Complexity:
Comments