c++ - Throwing the fattest people off of an overloaded airplane.

Question

Let's say you've got an airplane, and it is low on fuel. Unless the plane drops 3000 pounds of passenger weight, it will not be able to reach the next airport. To save the maximum number of lives, we would like to throw the heaviest people off of the plane first.

And oh yeah, there are millions of people on the airplane, and we would like an optimal algorithm to find the heaviest passengers, without necessarily sorting the entire list.

This is a proxy problem for something I'm trying to code in C++. I would like to do a "partial_sort" on the passenger manifest by weight, but I don't know how many elements I'm going to need. I could implement my own "partial_sort" algorithm ("partial_sort_accumulate_until"), but I'm wondering if there's any easier way to do this using standard STL.

Answer 1

This won't help for your proxy problem, however:

For 1,000,000 passengers to drop 3000 pounds of weight, each passenger must lose (3000/1000000) = 0.003 lbs per person. That could be achieved through jettisoning every ones shirt, or shoes, or probably even fingernail clippings, saving everyone. This assumes efficient collection and jettison before the weight loss needed increased as the plane used more fuel.

Actually, they don't allow fingernail clippers on board anymore, so that's out.