You are not logged in.
Pages: 1
Suppose we are given a list of n people who want to fly to the moon (and return). Person i
has priority pi and they weigh wi pounds. You may assume all of the priorities are different.
Our spaceship can carry at most k pounds which is, unfortunately, smaller than the total
weight of all the people. If priority pi > pj then if we take person j we must take person i.
Describe an algorithm that runs in O(n) (linear) time that finds the largest set of people we can fly to
the moon without exceeding the weight limit.
We fly everyone with priority greater than p(m).
Hint: Use recursion. How can you use the linear time k-select algorithm to insure that the
subproblems are small?
k-select returns the kth smallest element in linear time. (so if you have 1,2,3,4,5,6,7,8,9 kselect(3) will return 3)
Last edited by fusilli_jerry89 (2009-10-15 17:58:27)
Offline
o wow this is a hard one jerry good luck bro.
Offline
I tried a few ways. but I always get N^2 or more
Offline
Pages: 1