Throwing the fattest people off of an overloaded airplane.
One way would be to use a min heap (std::priority_queue
in C++). Here's how you'd do it, assuming you had a MinHeap
class. (Yes, my example is in C#. I think you get the idea.)
int targetTotal = 3000;
int totalWeight = 0;
// this creates an empty heap!
var myHeap = new MinHeap<Passenger>(/* need comparer here to order by weight */);
foreach (var pass in passengers)
{
if (totalWeight < targetTotal)
{
// unconditionally add this passenger
myHeap.Add(pass);
totalWeight += pass.Weight;
}
else if (pass.Weight > myHeap.Peek().Weight)
{
// If this passenger is heavier than the lightest
// passenger already on the heap,
// then remove the lightest passenger and add this one
var oldPass = myHeap.RemoveFirst();
totalWeight -= oldPass.Weight;
myHeap.Add(pass);
totalWeight += pass.Weight;
}
}
// At this point, the heaviest people are on the heap,
// but there might be too many of them.
// Remove the lighter people until we have the minimum necessary
while ((totalWeight - myHeap.Peek().Weight) > targetTotal)
{
var oldPass = myHeap.RemoveFirst();
totalWeight -= oldPass.Weight;
}
// The heap now contains the passengers who will be thrown overboard.
According to the standard references, running time should be proportional to n log k
, where n
is the number of passengers and k
is the maximum number of items on the heap. If we assume that passengers' weights will typically be 100 lbs or more, then it's unlikely that the heap will contain more than 30 items at any time.
The worst case would be if the passengers are presented in order from lowest weight to highest. That would require that every passenger be added to the heap, and every passenger be removed from the heap. Still, with a million passengers and assuming that the lightest weighs 100 lbs, the n log k
works out to a reasonably small number.
If you get the passengers' weights randomly, performance is much better. I use something quite like this for a recommendation engine (I select the top 200 items from a list of several million). I typically end up with only 50,000 or 70,000 items actually added to the heap.
I suspect that you'll see something quite similar: the majority of your candidates will be rejected because they're lighter than the lightest person already on the heap. And Peek
is an O(1)
operation.
For a more information about the performance of heap select and quick select, see When theory meets practice. Short version: if you're selecting fewer than 1% of the total number of items, then heap select is a clear winner over quick select. More than 1%, then use quick select or a variant like Introselect.
What is your favorite phrase, saying, or quote expressed as code?
This simple expression is about as compact as I know...
2B || !2B
Or as a regex
/(bb|[^b]{2})/
In an integer array with N elements , find the minimum k elements?
If K << N, min heap is good enough because creation of heap is O(n), and if K << N selecting first K items is at most O(N), otherwise you could use selection algorithm to find Kth smallest element in O(n)
then select numbers which are smaller than found item. (Sure if some numbers are equal to Kth element select till fill K
items).
(C++) multiplication wont give off expected results
Your constructor assigns values to the passed arguments.
Try this instead:
class Box
{
public:
double length;
double breadth;
double height;
Box(double l, double b, double h)
{
length=l;
breadth=b;
height=h;
}
};
As others have mentioned, there are other improvements that can be made regarding initializer lists and the use of using
, and the study of programming in general and c++ in particular is an ongoing journey, never a destination, but this is the direct fix for the immediate problem.
Related Topics
How to Detect Negative Numbers as Parsing Errors When Reading Unsigned Integers
How to Design Proper Release of a Boost::Asio Socket or Wrapper Thereof
How to Make Sure That Std::Random_Shuffle Always Produces a Different Result
Vc2013: Function from Bind Not Compiling
Programmatically Check Whether My MAChine Has Internet Access or Not
Rc.Exe No Longer Found in VS 2015 Command Prompt
Gcc Std::Thread Not Found in Namespace Std
C++ Access Violation Reading Location 0Xcdcdcdcd Error on Calling a Function
Is Uninitialized Data Behavior Well Specified
When Does an Incomplete Type Error Occur in C++
Remove Duplicates from a List<Int>
Move Element from Boost Multi_Index Array
Auto Keyword Behavior with References
Will Memcpy or Memmove Cause Problems Copying Classes