Throwing the fattest people off of an overloaded airplane.

Why don't you use a partial quicksort with a different abort rule than "sorted". You can run it and then use just the higher half and go on until the weight within this higher half does not contain the weight that has at least to be thrown out anymore, than you go back one step in the recursion and sort the list. After that you can start throwing people out from the high end of that sorted list.

Here's a heap-based solution using Python's built-in heapq module. It's in Python so doesn't answer the original question, but it's cleaner (IMHO) than the other posted Python solution.

import itertools, heapq

# Test data
from collections import namedtuple

Passenger = namedtuple("Passenger", "name seat weight")

passengers = [Passenger(*p) for p in (
    ("Alpha", "1A", 200),
    ("Bravo", "2B", 800),
    ("Charlie", "3C", 400),
    ("Delta", "4A", 300),
    ("Echo", "5B", 100),
    ("Foxtrot", "6F", 100),
    ("Golf", "7E", 200),
    ("Hotel", "8D", 250),
    ("India", "8D", 250),
    ("Juliet", "9D", 450),
    ("Kilo", "10D", 125),
    ("Lima", "11E", 110),
    )]

# Find the heaviest passengers, so long as their
# total weight does not exceeed 3000

to_toss = []
total_weight = 0.0

for passenger in passengers:
    weight = passenger.weight
    total_weight += weight
    heapq.heappush(to_toss, (weight, passenger))

    while total_weight - to_toss[0][0] >= 3000:
        weight, repreived_passenger = heapq.heappop(to_toss)
        total_weight -= weight


if total_weight < 3000:
    # Not enough people!
    raise Exception("We're all going to die!")

# List the ones to toss. (Order doesn't matter.)

print "We can get rid of", total_weight, "pounds"
for weight, passenger in to_toss:
    print "Toss {p.name!r} in seat {p.seat} (weighs {p.weight} pounds)".format(p=passenger)

If k = the number of passengers to toss and N = the number of passengers, then the best case for this algorithm is O(N) and the worst case for this algorithm is Nlog(N). The worst case occurs if k is near N for a long time. Here's an example of the worst cast:

weights = [2500] + [1/(2**n+0.0) for n in range(100000)] + [3000]

However, in this case (throwing people off the plane (with a parachute, I presume)) then k must be less than 3000, which is << "millions of people". The average runtime should therefore be ab