Consider an example [1,2,4,3,3]

Greedy algorithm works like this: Take in the maximum item first in the reverse sorted list: [4,3,3,2,1]

Now, we have i as 4 and j as 1. So, residual is 0. So, it does not enter the second loop. Then we have 3. As inp[j](--> 1) < resid(--> 1), resid would be 0 after decrementing. So, count = 2 The procedure goes on.

Remember, if only the second loop is satisfied, the last(least) number is included, else the biggest numbers are taken in (Greedy, ain't it!).

Why the answer for 3 3 2 is 3 instead of 2 ?

they have to go in groups thats why 3. answer will be 2 when u break there groups

One taxi can include more than 1 group and it means if u have 1, 1 , 1 ,1 and the sum of nums is = 4 so the output must be 1 but when 3 3 2 so u don't have any sum of 2 groups = 4 that means u can't do 3+3+2/4 because u will lose that each group must be in the same taxi.

The problem says that one taxi can accumulate 4 people and all members of a group can't be divided . so 1st taxi can accumulate 3 people so that taxi has only one seat empty.but there is no groups of one members. then 2nd taxi can be filled as 1st one .One group remain with two members they can't be divided so another taxi is needed .thus 3 taxi is the output

three number group can not break,,,so they need another group

Heh, Last seen was 16 months ago. Why bother?