LC: 774. Minimize Max Distance to Gas Station - spiralgo/algorithms GitHub Wiki

774. Minimize Max Distance to Gas Station:

The Essence:

At the first glance, one might not get the point of why this question is hard. The reason is also the essence of the problem:

• In the beginning, there is a maximum distance (penalty) between two of the original stations.
• We want to minimize it by placing a new station between those stations.
• But when we minimize this distance, another interval between other original stations will have the maximum distance.
• It means, the interval that has the maximum distance will keep changing at each placement. That is what makes the question hard.

Details:

Therefore, we find a way to find an algorithm like a placement plan in order to yield the minimum distance.

• We can use a PriorityQueue to always get the interval that has the maximum distance at that moment.
• We can use Binary Search to test if a minimum distance is possible. So it will be like a trial-and-error technique empowered with Binary Seach's divide-and-conquer strategy.

You can find the detailed explanation for both implementations here: https://github.com/spiralgo/algorithms/pull/311