Task Assignment

Tags

Task Assignment

Category

Greedy

Difficulty

Medium

Problem Statement

Given an integer k representing the number of workers and an array of positive integers representing task durations, assign exactly two tasks to each worker. The goal is to minimize the maximum total duration assigned to any single worker. Each task must be assigned to exactly one worker, and each worker gets exactly two tasks. Return the optimal pairing of task indices.

Intuition

The worker who finishes last determines the total completion time. To minimize this maximum, we want to balance the workload. Pairing the longest task with the shortest task, the second longest with the second shortest, and so on, achieves the best balance. This works because the longest task cannot be avoided, and pairing it with the shortest minimizes its combined weight.

Approach

  1. Create an array of (duration, originalIndex) pairs to preserve original indices.
  2. Sort this array by duration in ascending order.
  3. Pair the first element with the last, the second with the second-to-last, and so on.
  4. Each pair forms the two tasks assigned to one worker.
  5. Return the list of index pairs.

Pseudocode

function taskAssignment(k, tasks):
    indexedTasks = [(tasks[i], i) for i in range(length(tasks))]
    sort(indexedTasks by duration)

    pairs = []
    for i from 0 to k - 1:
        leftIndex = indexedTasks[i].index
        rightIndex = indexedTasks[2 * k - 1 - i].index
        pairs.append([leftIndex, rightIndex])

    return pairs

Time & Space Complexity

  • Time: O(n log n) where n is the number of tasks (n = 2k). Sorting dominates.
  • Space: O(n) for the indexed tasks array.

Key Insights

  • This is a classic min-max pairing problem. The greedy approach of pairing smallest with largest is provably optimal.
  • Proof sketch: if the longest task were paired with anything other than the shortest, we could swap to reduce the maximum pair sum.
  • The total number of tasks is always exactly 2k.
  • We must track original indices since sorting changes the order.

Edge Cases

  • Single worker (k = 1): assign both tasks to that worker; the pairing is the only option.
  • All tasks have the same duration: any pairing is optimal.
  • Two tasks with very different durations: pairing the extreme values together balances the load.
  • Tasks already sorted: the pairing still follows the same first-with-last strategy.

Linked mentions