Greedy Algorithms in Python: Optimal Task Assignment

[@KippiExplainsStuff]

First off, the explanation about ~0 is brilliant! I feel like I've gained a new tool as a programmer. Thanks for that! Secondly - this needs to be said - this solution will not work for an odd number of tasks. I checked to make sure. one task won't be assigned a worker. What I did was to add a check to see if there are odd or even number of tasks. If it's odd, I first assign a worker only the last task (I did the assignments as tuples) and then did the rest. I actually didn't print, rather just returned a list of tuples.If I assigned the last task (i take the last one because bu itself is probably closer to the average of the rest) i popped it before getting to the loop. here is my code: def optimal_task_assignment(tasks): workers = [] tasks = sorted(tasks) if len(tasks) % 2 == 1: workers.append((tasks[-1],)) tasks.pop() for i in range(len(tasks) //2): workers.append((tasks[i], tasks[~i])) return workers

[@LucidProgramming]

Hi Amos. Thanks as always for your commentary! I appreciate you improving upon the solution to work for a broader case. Thanks very much for that, and if you feel like improving the code on my Github, feel free to make a pull request, and I can add your code in the repo. In any case, thanks very much for your comment!

[@KippiExplainsStuff]

@@LucidProgramming I'd be happy to, in a few days, once I've had my interview :P

[@LucidProgramming]

@@KippiExplainsStuff Best of luck with your interview, Amos!

[@thedumbfounds767]

great video! This seems to be a quite practical algorithm for many use cases. I am wondering, how would you approach assigning an odd number of tasks to each worker?

[@vernongriesel3910]

For this example each worker needed to do 2 jobs, so an odd amount of jobs was not an option. Let's assume that there were an odd number of jobs, you could assign 1 worker with the biggest job and then continue to do the greedy algorithm OR possible assign 1 worker with 3 of the smallest jobs and then continue the greedy approach. That doesn't scale well, and especially won't work in this example. This approach also assumes that the values don't deviate much from each other either. So while this is a very useful, it is not robust by itself. Nice video btw, really good explanation.

[@jeetshah8513]

what is the length of the array is an odd number will we just add a zero in the beginning?

[@LucidProgramming]

No, it should work in the odd case.

[@mr.banana5718]

Sir, what if the number of tasks is odd ???

[@josephoduor5322]

A=[6,3,2,7,5,5] A= sorted (A) for i in range(len(A)//2): print(A[i],A[-i]) I got (2,2)(3,7)(5,6)

[@LucidProgramming]

Hi Joseph. Your code is wrong. It should be "~" instead of "-".

[@Joni2Back]

It is print(A[i], A[~i])

[@LucidProgramming]

@@Joni2Back Yep. That's what I commented 2 months ago :P. Thanks all the same though!

[@Joni2Back]

@@LucidProgramming omg sorry didn't see

[@LucidProgramming]

@@Joni2Back Np :P

[@alexisjulian8316]

It really helps me in Assignment :D My only problem is how to put those arrays into worker 1 - worker 3 so it can be understandable by the reader

[@LucidProgramming]

Thanks, glad it helped. Couldn't you just add that to the print statement to solve your problem?

[@argorninc]

Thanks. can you help me to modify the code for a case where one worker is suppose to complete the load

[@LucidProgramming]

Hi Kweku. No problem. If you would like me to make a video and solve for a specific case, you can request that on my Patreon page. Every little bit helps support my channel, and I really appreciate any support that can be provided! Thanks: www.patreon.com/lucidprogramming

[@mohamedsadik84]

great work man Keep them coming

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support, and if you want to support the channel, I do have a PayPal link (paypal.me/VincentRusso1 ) for donations that go directly to the creation of content on this channel. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@alalehrazmjoo2850]

@@LucidProgramming Hi there, the PayPal link is broken! Thanks a lot for the great content, I am going through them while I am getting prepared for interviews.

[@LucidProgramming]

@@alalehrazmjoo2850 Oh, whoops! Thank you for letting me know about that. I went ahead and fixed it so that it directs to paypal.me/VincentRusso1. Thanks again or letting me know, and best of luck with your interviews!

[@mariano3395]

Dynamic programming problem solving would be appreciated! Thanks

[@tareqoweinat5952]

intuitive , thank you very much

[@vivekanandsahu2631]

This algorithm will not always work! e.g [1,2,2,3,4,8] gives (9,6,5) but the best ans will be (8,6,6)

[@EvilsoriHC]

Hi! I suppose you mean that the 1st worker does the 8-hour task, second does 1+2+3 hour tasks, and the 3rd does 2+4. You got a point and your answer seems to be more optimized for workers. However, You might have misunderstood the problem: each of the three workers has to do EXACTLY two tasks, not three tasks and not only one task. That’s why you can’t get (8,6,6). I hope i explained it well and you will understand :) have a nice day

[@vivekanandsahu2631]

Got that.

[@sai-du6qg]

Hey help me with this problem. Given an array of Integers , you need to find the maximum we can get . If we select some integer we need to add equal value until end and return the maximum we can get. Some test cases are Arr - [ 4,80,84] Ans - 160 Arr- [ 90, 8,30] Ans - 30 Arr-[ 40,20,60] Ans - 60

[@LucidProgramming]

What have you tried so far?

[@8koi139]

I only needed 40 seconds to came up whit a solution to my problem lol. I just added an if to force the function to be greedy

[@javadkhalilarjmandi3906]

perfect, but I have one problem, how can I assign these pears, each to the certain worker, because worker's performance are different(in my case)

[@LucidProgramming]

Hi Javad. I'm not sure I understand your question. You want to perform an optimal assignment of paired tasks? Can you elaborate more on the problem so that I can try to help? Cheers, and thanks for watching.

[@javadkhalilarjmandi3906]

really thanks for replay, here is my problem, making pear of tasks which you explained very well, but I have three stations (workers)that their performance is not like each other and one is faster than other,so i wanna assign two pears to one station and one other pear to two other stations, we have three pears but i wanna give two of them to just one worker because his performance is faster(4 time faster, in this example) than other stations,thx again:-)

[@LucidProgramming]

Hi Javad. There are quite a few variations that one can have on this problem, and the greedy method may not always be the appropriate approach. There are some properties that this problem has that make it particularly amenable to such a strategy. I would suggest you look up "assignment optimization", specifically the Wikipedia page. Try to come up with a formula for your case based on the information you read there. Then, see if you can write a solution. Let me know how your process goes, but I encourage you to actually sit down and think it through. Don't worry about giving the problem your time and attention, it's worth it to learn.

[@javadkhalilarjmandi3906]

tnx for your help, sure I will try.I must fix this problem!again tnx

[@LucidProgramming]

It's a gradual process. Keep at it. You'll get it. Thanks again for watching.

[@amanjhurani6178]

Which text editor you are using?

[@LucidProgramming]

vim. All the information for that is in the description of this video.

[@amanjhurani6178]

@@LucidProgramming Why you stopped making videos? Your videos are so much informative.

[@LucidProgramming]

@@amanjhurani6178 Thanks. I want to start up again. My schedule has been a bit rough these days. It's nice to know other people find these videos useful and informative. Thanks for that.

[@amanjhurani6178]

@@LucidProgramming Great, we will wait for something exciting.

[@LucidProgramming]

@@amanjhurani6178 Hoping there is something soon. Cheers!

[@harrydadson7467]

I'm confused why do we divide the range by 2...please let me know thank you

[@LucidProgramming]

I think this is explained in the slide portion of the video, right?

[@harrydadson7467]

@@LucidProgramming That was pretty fast thanks but isnt range(len(a)//2) = 3 --> (0,1,2)

[@LucidProgramming]

@@harrydadson7467 I don't understand what (0,1,2) has to do with it. The division will give you an integer.

[@jackb7620]

because we only need to enter the loop three times (in this scenario), because each time we iterate, we pop the first AND the last item of the array. So if we have [1,2,3,4,5,6], it will look like this: Begin: [1,2,3,4,5,6] 1st iteration completed: [2,3,4,5] 2nd iteration completed [3,4] 3rd iteration completed: [] So now the array is empty, even though we only iterated half the times (3 iterations on an 6-element-array)

[@LucidProgramming]

@@jackb7620 Thanks for the added clarification, Jakokb!

[@louielogn6117]

Is the slides available ?

[@LucidProgramming]

Description has been updated with a link to the slides.

[@louielogn6117]

@@LucidProgramming ​ Thanks for all hard work u doing in this channel

[@LucidProgramming]

@@louielogn6117 Cheers, and thanks for the support.

[@devendratapdia11]

Awesome

[@LucidProgramming]

Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing! I really appreciate the support, and if you want to support the channel, I do have a PayPal link (www.paypal.me/VincentRusso1) for donations that go directly to the creation of content on this channel. I hope that the content I provide there will enhance the videos on my KZbin page. bit.ly/lp_email

[@isaacyoon3926]

Khan is this you?

[@LucidProgramming]

Haha, Salman Khan? Afraid not :)