Spoilers here if you don’t want any hints.
…
Regarding this problem, I looked up the way to do it and I have a basic understanding that you do a binary search on the maximum waiting time M.
I understand that to check whether M works, you simulate the process. As you fill each bus you wait as long as possible (within given M) to send it off.
What I would like to understand better is why it always gives the correct answer (“works” or “not works”) by waiting as long as possible to send a bus. I mean, intuitively it makes sense, but I’m wondering about a formal proof. I’d like to know if this idea works:
Let’s suppose there that by filling a bus to the max, you cause a problem later in the chain (you cause some buses waiting time to exceed M) so you MUST send it early. But you could always fill a bus to the max and then send the next bus early, contradicting the assumption that you MUST send it early.
Proof by contradiction? Is this all that is necessary?