Greedy Algorithms in Python: Optimal Task Assignment

This video is sponsored by Oxylabs. Oxylabs provides market-leading web scraping solutions for large-scale public data gathering. You can receive data in JSON or CSV format and pay only per successful request. At the moment, Oxylabs offers a free trial.

In this video, we will be solving the following problem:

We wish to determine the optimal way in which to assign tasks to workers. Each worker must work on exactly two tasks. Tasks are independent and each task takes a fixed amount of time.

Problem:
Assign tasks to workers such that the time it takes to complete all tasks is minimized.

Slides:

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[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
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

[thedumbfounds]

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?

[josephoduor]

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)

[mr.banana]

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

[jeetshah]

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

[mariano]

Dynamic programming problem solving would be appreciated! Thanks

[alexisjulian]

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

[argorninc]

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

[vivekanandsahu]

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)

[koi]

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

[sai-duqg]

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

[javadkhalilarjmandi]

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)

[harrydadson]

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