Maximum Number of Tasks You Can Assign — Hard Problem & Solution

Task i needs strength tasks[i]; worker j has strength workers[j].

Difficulty: Hard
Topics: Arrays, Greedy, Sorting, Binary Search, Queue
Asked at: Amazon, Google, Databricks
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Task i needs strength tasks[i]; worker j has strength workers[j]. Each worker takes at most one task, and can take task i only if their strength is at least tasks[i].

You also have pills magical pills; giving one to a worker raises their strength by strength permanently. Each worker takes at most one pill. Return the maximum number of tasks that can be assigned.

Example 1

Input: tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
Output: 3
Explanation: Pill the strength-0 worker to handle task 1.

Example 2

Input: tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
Output: 1

Example 3

Input: tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
Output: 2

Constraints

1 <= tasks.length, workers.length <= 1000
0 <= pills <= workers.length
0 <= tasks[i], workers[j], strength <= 1000000000

How to solve Maximum Number of Tasks You Can Assign

Binary search the number of tasks. For a fixed k, the choice of which tasks and workers to use is forced — the easiest tasks and the strongest workers — and then a greedy from the hardest task downwards, spending pills as late and as cheaply as possible, decides feasibility.

Approach

Sort both arrays. For a candidate k, take tasks[0 … k-1] and the top k workers.
Walk the chosen tasks from hardest to easiest. If the strongest free worker already qualifies, use them.
Otherwise spend a pill on the weakest free worker who qualifies with it — found by binary search — so stronger workers stay for harder tasks.
If no worker qualifies even with a pill, or pills run out, k is infeasible.

Why it works

Using the easiest tasks and strongest workers is an exchange argument: swapping in an easier task or a stronger worker never breaks a valid assignment. Within that, handling the hardest task first is forced because only the strongest workers can do it, and when a pill is needed the weakest qualifying worker is the right choice — spending the pill on anyone stronger wastes capacity that a harder task might have needed.

Complexity

Time — O(n log n + n² log n) at these limits
Space — O(n)

Pitfalls

Assigning the easiest task first, or pilling the strongest worker, both give wrong answers.
The strongest free worker must be checked before reaching for a pill, or pills get wasted.
workers[j] + strength reaches 2 · 10^9 — the comparison needs 64-bit in languages where int is 32-bit.

Reference solution

Python

from typing import List

def maxTaskAssign(tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
    t = sorted(tasks)
    w = sorted(workers)

    def check(k: int) -> bool:
        left = pills
        avail = w[len(w) - k:]
        for i in range(k - 1, -1, -1):
            need = t[i]
            if avail and avail[-1] >= need:
                avail.pop()
                continue
            if left == 0:
                return False
            lo, hi = 0, len(avail)
            while lo < hi:
                mid = (lo + hi) // 2
                if avail[mid] + strength >= need:
                    hi = mid
                else:
                    lo = mid + 1
            if lo == len(avail):
                return False
            avail.pop(lo)
            left -= 1
        return True

    lo, hi, ans = 0, min(len(t), len(w)), 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid == 0 or check(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

JavaScript

var maxTaskAssign = function(tasks, workers, pills, strength) {
    var t = tasks.slice().sort(function(a, b) { return a - b; });
    var w = workers.slice().sort(function(a, b) { return a - b; });
    var check = function(k) {
        var left = pills;
        var avail = w.slice(w.length - k);
        for (var i = k - 1; i >= 0; i--) {
            var need = t[i];
            if (avail.length > 0 && avail[avail.length - 1] >= need) { avail.pop(); continue; }
            if (left === 0) return false;
            var lo = 0, hi = avail.length;
            while (lo < hi) {
                var mid = (lo + hi) >> 1;
                if (avail[mid] + strength >= need) hi = mid; else lo = mid + 1;
            }
            if (lo === avail.length) return false;
            avail.splice(lo, 1);
            left--;
        }
        return true;
    };
    var low = 0, high = Math.min(t.length, w.length), ans = 0;
    while (low <= high) {
        var m = Math.floor((low + high) / 2);
        if (m === 0 || check(m)) { ans = m; low = m + 1; } else high = m - 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue