Dawny33's blog

By Dawny33, 6 years ago, In English,

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!).

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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