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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.