Optimal Task Assignment
Explore how to optimally assign tasks to workers by pairing longest and shortest tasks using a greedy algorithm. Understand the time complexity and implement the solution in Python with clear explanations and code examples.
We'll cover the following...
In this lesson, we will be solving the following problem:
Assign tasks to workers so that the time it takes to complete all the tasks is minimized given a count of workers and an array where each element indicates the duration of a task.
We wish to determine the optimal way in which to assign tasks to some workers. Each worker must work on exactly two tasks. Tasks are independent of each other, and each task takes a certain amount of time.
In the slides below, we have been given an array of tasks where the value of each element in the array corresponds to the number of hours required for each task.
Check out the slides below where an example of assigning tasks optimally to workers has been illustrated:
Now let’s think of a general approach. From the above example, we know that we have to make pairs. If we generate all possible pairs, it would not be efficient as enumerating every possible pair would require generating ...