Some typos in my solution :( Use a Max heap.. first take the first 10 stations and build a* Max *heap O(10)..Heap contains distance between 2 stations . Initial Heap will contain 10 *minimum *distances with maximum of those at the top . Now 11 th comes u compare with the root of the heap . If its less than that than replace it with the top and run heapify (O(log10) ) ..keep doing the same . In the end u have 10 stations with min distance between them
Complexity O(10) + O(log(10)) = O(1) ..Comparision takes constant time So total complexity O(1) Regards Ankur On Sat, Sep 17, 2011 at 5:00 AM, Dave <[email protected]> wrote: > @Pankaj: Let's number the stations from 0 to 101, where stations 0 and > 101 are the end stations and stations 1 through 100 are the > intermediate stations. Let a[i], i = 1, 2, ..., 100 be the distance of > station i from station 0, and finally assume that the a's are > increasing, i.e., that the stations are presented in order. We want to > find i[1], i[2], ..., i[10] such that 0 = i[0] < i[1] < i[2] < ... < > i[10] < i[11] <= 101. Given any x, 0 < x <= a[101] (the distance > between the end stations), we can find the last station that is within > x of station 0. Call this station i1. In other words, a[i1] <= x but > a[i1+1] > x. Now find the last station that is within x of station > i[1] and call it i[2]. Etc until you find the last station that is > within x of station i10. If you get to station 101 in the process, the > rest of the i's = 101. This can be done with a linear search in > O(100), or using 10 binary searches in O(10 log 100). Now the problem > is to find the smallest x such that I[11] = 101. We can do this with a > binary search on x. Initialize xmin = a[101]/11 (that would have the > 10 intermediate stations equally spaced) and xmax = a[101] and begin a > loop. Let x = xmin + (xmax - xmin)/2. If x == xmin or x == xmax, > break; xmax is the minimax distance between stations and i[1], ..., > i[10] are the stations. Otherwise, calculate i[1] through i[11] as > above. If i[11] < 101, then x is too small, so set xmin = x and loop. > If i[11] = 101, then x is too large, so set xmax = x and loop. > > Dave > > On Sep 16, 1:22 pm, pankaj kumar <[email protected]> wrote: > > You are given two end points ( consider them as two end stations > > at some distance ) there are 100 stations between these two . Now you > > need to build a train track between these two end points which > > includes only 10 stations and not more than that . Now the objective > > is to find such 10 stations such that the maximum distance between any > > two consecutive stations is minimum . > > > > mine solution is > > > > find all possible subset of 10 elements and answer is that subset > > for which sum (of distance between > > consecutive stations )is minimum.. > > is it correct or any other solution. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > 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. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
