Loading...
Loading...
Loading...
A highway has outlets of k different food chains. For each chain you know the kilometre markers of its outlets, in sorted order. Markers are measured from a toll plaza, so they can be negative.
The food blogger Kavya wants to drive along the shortest stretch of highway [a, b] that passes at least one outlet of every chain. A stretch includes both of its ends.
Print a and b. If several stretches are equally short, print the one with the smallest a.
Example 1
Input
3 5 4 10 15 24 26 4 0 9 12 20 4 5 18 22 30
Output
20 24
The stretch [20, 24] holds 24, 20 and 22, one from each chain. No shorter stretch works.
Example 2
Input
2 2 1 10 2 2 11
Output
1 2
[1, 2] and [10, 11] are both 1 km long. The tie goes to the smaller a.
Try the problem first. Open one hint at a time.
A stretch is decided by the values it uses: one from each chain. It runs from the smallest of them to the largest.
Start with the first value of every chain. To make the stretch shorter, the only useful move is to replace the smallest value with the next value from its chain.
Repeat that move and track the best stretch. You need the smallest of k values again and again, and the largest only grows.
Keep one value per chain in a min-heap (PriorityQueue) and the current maximum in a variable. Stop when the chain of the smallest value runs out.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor