Hi,
I have a question regarding a recommendation made in the book. If the list of buildings is not sorted based on distances, one can use quickselect to find the appropriate building in O(n).
While this sounds interesting, I cannot currently see a way in which I can turn quickselect into something usable for this problem.
I can implement the pivot function which arranges the list according to the pivot. Regarding the select function, I cannot see the way in which to code the stop condition. Usually the quickselect stops when the new pivot index is the one sought. Here I should stop only when the residents of the sorted buildings add up to the given value…
Probably I should choose in select the lowest unvisited branch.
