Given each cow's maximum tolerated queue length, choose an arrival order that minimizes how many cows end up waiting in line.
Medium4GreedySortingArrayImplementationInterviewNo attempts yetTime limit2sMemory limit512 MBIt is a hot summer day on the farm, and Farmer John is serving lemonade to his N cows. Every cow likes lemonade, but some like it more than others. The cows are numbered 1 through N, and cow i is willing to wait in line behind at most wi other cows to get her lemonade.
Right now all N cows are out in the fields. As soon as Farmer John rings his cowbell, the cows head straight for the lemonade stand. They all arrive before he starts serving, and no two cows arrive at the same time. When cow i arrives, she joins the line if and only if at most wi cows are already in it. Otherwise she turns away.
Farmer John wants to prepare the lemonade in advance without wasting any. The number of cows who join the line depends on the order in which they arrive. Find the smallest number of cows who can end up in the line.
The first line contains N. The second line contains the N space separated integers w1,w2,…,wN. It is guaranteed that 1≤N≤105 and that 0≤wi≤109 for each cow i.
Print, on one line, the smallest number of cows who join the line, taken over all possible arrival orders.
In the first example only three cows end up in line, and no arrival order does better. Suppose the cows with w=7 and w=400 arrive first and wait in line. The cow with w=1 then arrives and turns away, since two cows are already in line. The two cows with w=2 arrive last, one staying and one turning away.