Katkat
Back

Minimize time for two handlers

AmazonSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to use dynamic programming or greedy strategies with state tracking to minimize the total completion time of tasks assigned to two distinct handlers.

Minimize Time for Two Handlers

You are managing two handlers, A and B, who must process a sequence of n tasks. Each task i has a processing time T[i]. The handlers can work simultaneously, but each handler can only process one task at a time.

When a task is assigned to a handler, the handler remains busy for T[i] units of time. Once a handler finishes a task, it is immediately available for the next task assigned to it. You must assign every task in the sequence to either handler A or B such that the tasks are processed in their original order. The goal is to minimize the time at which the last task is completed (i.e., max(finish_time_A, finish_time_B)).

Function Signature

def minimize_completion_time(tasks: List[int]) -> int:

Constraints

  • n (number of tasks) is between 1 and 1000.
  • T[i] (processing time) is between 1 and 100.

Examples

Example 1: Input: tasks = [3, 5, 2] Output: 5 Explanation: Assign task 1 (3) to A, task 2 (5) to B, and task 3 (2) to A. A finishes at 3+2=5, B finishes at 5. The max is 5.

Example 2: Input: tasks = [10, 20, 30] Output: 30 Explanation: Assign 10 to A, 20 to B, and 30 to A. A finishes at 10+30=40, B finishes at 20. Wait, if we assign 10 and 20 to A, A finishes at 30, B finishes at 30. Output is 30.

Edge Cases

  • Single task: The completion time is just the duration of that task.
  • All tasks equal: Distribute as evenly as possible.

Hints

Hint 1

Note that the finish time of one handler is determined by the sum of tasks assigned to it, but the total completion time is the maximum of the two handlers' workloads.

Hint 2

Consider using dynamic programming where the state is defined by the current task index and the accumulated time of one handler.

Hint 3

Since the total time spent by both handlers is constant (sum of all T[i]), if you know the total time of handler A, you automatically know the total time of handler B.

Follow-up questions

  • How would your approach change if there were three handlers instead of two?
  • If the handlers had different processing speeds (e.g., A is twice as fast as B), how would the state space change?
  • Can you optimize the space complexity of your DP solution from O(n * total_sum) to something smaller?