Optimal Task Assignment

February 4, 2024

Problem Statement #

You are given a list of tasks where each task has a duration. Your goal is to assign these tasks to workers so that all tasks are completed while minimizing the total time. Each worker must work on exactly two tasks and can only work on one task at a time. Return the optimal assignment of tasks.

Example:

1. Input: tasks = [6, 3, 2, 7, 5, 5] Output: [(2, 7), (3, 6), (5, 5)] Explanation: Pairing the tasks in this way results in the minimum total duration: 9, 9, and 10. The maximum pair duration is 10, which is the minimum possible.

Solution Approach #

The solution involves sorting the tasks and pairing the shortest task with the longest task to minimize the maximum duration taken by any worker.

Algorithm Steps #

1. Sort the task durations in ascending order.
2. Create pairs of tasks by pairing the first task (shortest duration) with the last task (longest duration) until all tasks are paired.
3. Return the list of task pairs.

Code (Python) #

def optimalTaskAssignment(tasks):
    tasks.sort()
    pairedTasks = []
    i, j = 0, len(tasks) - 1
    while i < j:
        pairedTasks.append((tasks[i], tasks[j]))
        i += 1
        j -= 1
    return pairedTasks

# Example usage
tasks = [6, 3, 2, 7, 5, 5]
print(optimalTaskAssignment(tasks))  # Output: [(2, 7), (3, 6), (5, 5)]

Time Complexity #

O(n log n), where n is the number of tasks. The sorting of the tasks is the most time-consuming part.

Space Complexity #

O(n), to store the result in a list of task pairs.