Minimum Time to Complete Tasks with K Workers

Problem

What are we solving?

Problem Statement

Given an integer array tasks where tasks[i] is the work required for task i, and an array speeds of worker speeds, assign contiguous blocks of tasks to workers. A worker with speed s assigned total work W finishes in time W / s. Return the minimum possible time needed to finish all tasks.

Example

Input:tasks = [3, 2, 5, 4, 1, 6], speeds = [2, 1, 3]

Output:5.0

Explanation:At T = 5, budgets are [10, 5, 15]. We can assign [3,2,5], [4,1], [6]. T = 4 fails, so 5.0 is the minimum feasible bound.

Intuition

Minimize the maximum — classic search on answer

We are not searching for a task assignment directly. We binary search a candidate time limit T and ask one yes/no question: if every worker is allowed at most T time, can the tasks be covered in order?

If time limit T works, every larger time also works. That false-to-true transition is exactly the shape binary search needs.

tasks=[3,2,5,4,1,6], speeds=[2,1,3] · Search space: T from 0 to sum(tasks)

condition: canFinish(T) — can all workers cover the tasks within time T?

T=2F

T=3F

T=4F

T=5T*

T=7T

T=10T

At T = 5, worker budgets are 10, 5, and 15. That is just enough to greedily cover all tasks in order. T = 4 is too tight, so the first true boundary is 5.

The feasibility check

Walk left to right through tasks. For a candidate time T, worker i can cover at most T × speeds[i] total work. Greedily give that worker as many consecutive tasks as fit; once the next task would overflow the budget, move to the next worker.

Worker	Speed	Budget at T=5	Tasks taken	Work used	Status
A	2	10	[3, 2, 5]	10	Fits
B	1	5	[4, 1]	5	Fits
C	3	15	[6]	6	Fits

→

Why greedy is correct: task order is fixed and assignments must be contiguous. Once a worker stops at task i, the next worker must start at i+1. There is no better rearrangement to search for, so greedily filling each worker’s budget is optimal for the feasibility check.

→

Closest LeetCode relative: this is structurally closest to LC 410 — Split Array Largest Sum. Both minimize the maximum load across contiguous blocks; this version adds worker speeds and makes the answer a floating-point time bound.

Solution

Clean implementation

class Solution {
    public double minTime(int[] tasks, int[] speeds) {
        double left = 0.0, right = 0.0;
        for (int t : tasks) right += t;  // speed 1 worker is a safe upper bound

        double eps = 1e-9;
        while (right - left > eps) {
            double mid = left + (right - left) / 2.0;
            if (canFinish(tasks, speeds, mid)) {
                right = mid;          // feasible — try tighter
            } else {
                left = mid;           // too small — need more time
            }
        }
        return right;
    }

    private boolean canFinish(int[] tasks, int[] speeds, double timeLimit) {
        int taskIdx = 0;

        for (int speed : speeds) {
            double budget = timeLimit * speed;
            double used = 0.0;

            while (taskIdx < tasks.length && used + tasks[taskIdx] <= budget) {
                used += tasks[taskIdx];
                taskIdx++;
            }

            if (taskIdx == tasks.length) return true;
        }
        return false;
    }
}

class Solution:
    def min_time(self, tasks: list[int], speeds: list[int]) -> float:
        left, right = 0.0, float(sum(tasks))
        eps = 1e-9

        while right - left > eps:
            mid = left + (right - left) / 2.0
            if self.can_finish(tasks, speeds, mid):
                right = mid
            else:
                left = mid
        return right

    def can_finish(self, tasks, speeds, time_limit):
        task_idx = 0

        for speed in speeds:
            budget = time_limit * speed
            used = 0.0

            while task_idx < len(tasks) and used + tasks[task_idx] <= budget:
                used += tasks[task_idx]
                task_idx += 1

            if task_idx == len(tasks):
                return True

        return False

Complexity

Time

O(n log S)

S = sum(tasks). Binary search performs a constant number of floating-point iterations, each with one O(n) greedy pass.

Space

O(1)

The feasibility check only tracks the current task index and worker budget.

→

Why floating-point binary search? the optimal time can be fractional, because a worker may finish a block in W / speed hours. So we search with an epsilon instead of integer boundaries.

Previous LC 410 — Split Array Largest Sum ↑ Pattern map Next problem LC 1482 — Min Days to Bloom