Use a Max heap.. first take the first 10 stations and build a min heap O(10)..Heap contains distance between 2 stations . Initial Heap will contain 10 min distances with highest 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 2:16 AM, Gene <gene.ress...@gmail.com> wrote: > All possible subsets of 10 elements is B(100,10), which is over 17 > trillion. Not a great algorithm. > > You can do this by constructing sets S_0, S_1, S_2, ... S_10, S_11 of > stations accessible from the start in 0,1,2,...10, 11 hops. The 11th > is from the final station to the destination. It's simple to construct > S_i+1 from S_i. I'll leave it to you. For each element of each S_i > it's also straightforward to keep track of the min of the max distance > that had to be traversed to get to there and a backward pointer to the > previous station on the best path. (A bit of care is needed for the > case where there's a cycle in the path. In this case a city may have > two or more predecessors!) After you've constructed S_11, look for the > destination there. If you find it, read off the path in reverse using > the back pointers. If it's not there, there exists no path of length > 10. > > If this sounds like Dijkstra's shortest path to you, you're onto > something. It's pretty close except that the concrete length of 10 > simplifies things. > > If you are interested in paths with fewer than 10 stations, that's a > simple modification I'll also leave to you. > > On Sep 16, 8:22 pm, pankaj kumar <p9047551...@gmail.com> 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 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. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
