EASY
The following greedy algorithm always finds the optimum answer:
Choose the lightest pie not yet on a rack
If none of the remaining racks can hold this pie, stop
Of all the racks that can hold this pie, place the pie on the rack with the smallest weight limit
If there are no more pies, stop. Otherwise, go back to step 1
Can be found here.
Hi
I had one query. Here you take the pies one by one and solve it via greedy algorithm. What if one takes it rack by rack. That is, i choose the first rack, see how many pies can be positioned on it and choose the one with the highest weight, and iterate over it. I could not think of a case where it should not work. But i wanted your take on it too?
That should work too
As the value of the number of pies and also the number of racks is equal to N.
So answer will never be greater than N so we can only check for number of pies fit into the racks
and print it.So that their is no need of checking of end of pies.If in case number of pies equals to N then all the racks get finished and answer will be N.
Means Simply as only one pies can be put in the rack if pies get finished rank will definitely get finished. So simply check for the end of racks and not about end of pies.
I don’t know greedy algorithm yet,I have a slightly simpler approach but I’m not able to get the correct answer, please give it read:
I take in the values of weights of pies in an array and weight limit in another.
I sort both the arrays using sort()
I run a loop from first to last, and if weight of pie>weight limit, counter++
I display (n-counter)
may i know what’s wrong with code??
The answer is 2?
@rohanndtuse
See why the logic is wrong.
Let the pies be 5 10.
Let the weight be 4 8.
Here, your code will return 0 but answer is 1.
5 can go in 8
@rohanndtuse
See why the logic is wrong.
Let the pies be 5 10.
Let the weight be 4 8.
Here, your code will return 0 but answer is 1.
5 can go in 8