PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Michael Nematollahi
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy
PREREQUISITES:
sorting
PROBLEM:
Chef is holding a party. He wants to invite N friends. However, his friends are demanding. The i_{th} friend states that if he arrives at Chef’s house and there are less than A_i people in the house (excluding Chef) he would just leave and never return back. Chef is wondering what’s the maximum number of friends that will attend the party. Chef is able to schedule the order of his friends’ arrivals. So you must help him to decide the best order of arrivals.
N \, \leq \, 10^5
EXPLANATION:
If we think a little bit, the best strategy is to invite friends sorted by their A values in ascending order. (Why?)
Suppose we have the x_{th} friend and the y_{th} friend such that A_x \, < A_y. It’s always better to invite the x_{th} one before. Because if we do the opposite, since A_x \, < A_y there’s a chance that the demand of y is not met and he leaves immediately. If we invite x before and he joins the party, we increase the number of people at the party getting close to y demand. On top of that, If we invite y before and he joins the party then x will join the party for sure (and this doesn’t make sense) so better to invite him before.
After we sort them according to A values, we iterate through friends list inviting them one by one. If the current friend can join the party, he’s welcome 
. Otherwise, we should just break and we have our answer (because all upcoming friends have larger demands so they would never be able to enter).
Since N may reach 10^5 we must use a fast sorting algorithm (merge sort, quick sort… etc).
You can use standard sort function in C++ or Java which runs in O(N \, log \, N).
Check implementations for more details.