This is a simple problem:
1. Understand that if you are selecting 2 petrol pumps, say P and Q with say
another petrol pump R between them, then it is optimal to include R into the
set of selected petrol pumps as the max-distance for the chosen pumps
remains PQ but number of included petrol pumps is reduced.
Diagram: P --- R --- Q
Therefore, all the selected pumps in the final solution are going to be
contiguous.
The simplest solution thus is to sort the points along the line AB. O(n log
n)
Then the answer is min{ai+10 - ai} for i = 0 to N-11 - O(n)
Therefore net complexity is O(n log n).
If the petrol pumps are given in sorted order from distance from A, then the
complexity is simply O(n).
--
DK
http://gplus.to/divyekapoor
http://www.divye.in
http://twitter.com/divyekapoor
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/m1jZuQUY85AJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
