it really gave clarity through that dry run!! , i think i mis-read the question though , . . . . .what i thought was -> , it was necessary that we have exgatly k employees selected ? our(your) code can give (maximum )answer even when we dont consider k people , but less than k people , , here is a test case . . . . eff = [100 , 1 , 1] , speed = [100 , 1 , 1 ] k = 3 , so we need 3 people but taking only the first guy gives us the answer as 100*100 , while taking all three of them reduces our answer to 1*(100+1+1)=102 , ,, , this is could be a variant to the original question , small change to our code like start taking maximum only when the size of heap has reached k should just do the thing!! Happy learning !
At any given step as we're traversing through that array "a", we know that the absolute best job we could do at that efficiency would be the sum of the prior 1-k total speeds. In my next step, my efficiency will be less than (or equal to) my previous efficiency, meaning that I know for a fact, once again, that my maximum performance would be the current efficiency times the prior 1-k total speeds. We rinse and repeat until completed! Doing the sort allows us to not have to do the brute force approach mentioned near the start of the video -- we pay up on the O(nlogn) cost up front to save from the exponential time operation of finding all combinations of 1-k workers for each efficiency.
You stopped an example on the most confusing part which is pair 3,3 In this case your heap would have 5,10,3 it's bigger than 2 so you drop the 3 and then in your code you do result = max(60,15*3(3 is efficiency=45) which still result 60 , but the thing is you still do a comparison even though 3 was dropped from the heap. Why greedy approach works here even though logically we should skip 45 and move further
Actually 3 is not dropped -- 2 would be dropped from the heap. We're using a MIN heap because we want to keep track of MAX values. I'm not sure I fully understand the question; we're not skipping through anything, as we actually walk through every single efficiency.
@@babybear-hq9yd 2 is the k, head has 5,10 then we add 3, size is bigger than 2 so we drop 3 but still check if 5+10*3 is bigger than 60(previous max value) it's logically incorrect
Just try to finish your example from scratchpad and you would see that logic is incorrect, but it still works , I have no clue how to prove this greedy solution
Great video, can you do an explanation on strobogrammatic number lll?
Great explanation :) expecting video for Minimum Difficulty of a Job Schedule
it really gave clarity through that dry run!! , i think i mis-read the question though , . . . . .what i thought was -> , it was necessary that we have exgatly k employees selected ? our(your) code can give (maximum )answer even when we dont consider k people , but less than k people , , here is a test case . . . . eff = [100 , 1 , 1] , speed = [100 , 1 , 1 ] k = 3 , so we need 3 people but taking only the first guy gives us
the answer as 100*100 , while taking all three of them reduces our answer to 1*(100+1+1)=102 , ,, , this is could be a variant to the original question , small change to our code like start taking maximum only when the size of heap has reached k should just do the thing!! Happy learning !
thanks
Hi Aleks, Thank you for your amazing videos. Could you also consider doing one on Remove Invalid Parentheses :)
thanks aparajita! I'll add it to the list -- I know that one's a bit of a bitch to solve
Great Explanation
Awesome! Thank you!!!!
Thanks!
welcome:)
so why does the logic of sorting the tuples by the max efficiency work, it isnt really explained in the videos. thanks
At any given step as we're traversing through that array "a", we know that the absolute best job we could do at that efficiency would be the sum of the prior 1-k total speeds. In my next step, my efficiency will be less than (or equal to) my previous efficiency, meaning that I know for a fact, once again, that my maximum performance would be the current efficiency times the prior 1-k total speeds. We rinse and repeat until completed! Doing the sort allows us to not have to do the brute force approach mentioned near the start of the video -- we pay up on the O(nlogn) cost up front to save from the exponential time operation of finding all combinations of 1-k workers for each efficiency.
You stopped an example on the most confusing part which is pair 3,3
In this case your heap would have 5,10,3 it's bigger than 2 so you drop the 3 and then in your code you do
result = max(60,15*3(3 is efficiency=45) which still result 60 , but the thing is you still do a comparison even though 3 was dropped from the heap. Why greedy approach works here even though logically we should skip 45 and move further
Actually 3 is not dropped -- 2 would be dropped from the heap. We're using a MIN heap because we want to keep track of MAX values. I'm not sure I fully understand the question; we're not skipping through anything, as we actually walk through every single efficiency.
@@babybear-hq9yd 2 is the k, head has 5,10 then we add 3, size is bigger than 2 so we drop 3 but still check if 5+10*3 is bigger than 60(previous max value) it's logically incorrect
Just try to finish your example from scratchpad and you would see that logic is incorrect, but it still works , I have no clue how to prove this greedy solution