So I am trying to solve a problem. I believe it is $NP$.
Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , can satisfy $S_i$ level of hunger. Each homeless person, $j$ requires $H_j$ hunger relief. The people and cans are not in any sorted order.
I would like to solve this problem in $O( P( \log(P) ) + F )$
The only thing that is coming to mind would be to sort all of the homeless people by level of hunger, ascending, and then satisfy each person with the cans of food until they reach their required level. I am not sure if there is a better solution, or how to describe the approximation ratio of this algorithm. The goal is to satisfy as many people's hunger as possible. We can not share cans, so there is possibly waste. Can anyone lend a hand/brain?
This actually sounds like something for which you would use the Hungarian Algorithm. You could use it to allocate cans to people. Note that the Hungarian Algorithm will allocate one can per person. After finding an initial optimal matching, you could remove satisfied people and used cans and re-run the algorithm. Below is a link with an explanation of the algorithm. Best of luck!
http://www.dreamincode.net/forums/topic/305150-data-structures-graph-theory-hungarian-algorithm/