Maximum Number of Tasks You Can Assign

Hard
838.

Maximum Number of Tasks You Can Assign

Maximum Number of Tasks You Can Assign is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Databricks interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} tasks
 * @param {number[]} workers
 * @param {number} pills
 * @param {number} strength
 * @return {number}
 */
var maxTaskAssign = function(tasks, workers, pills, strength) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Tasks You Can Assign — Problem & Solution

Maximum Number of Tasks You Can Assign solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Number of Tasks You Can Assign is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Databricks interviews.

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

Hints for Maximum Number of Tasks You Can Assign

  1. Hint 1

    If k tasks can be assigned, so can k - 1 — binary search k.

  2. Hint 2

    For a given k, always use the k easiest tasks and the k strongest workers.

  3. Hint 3

    Assign the hardest of those tasks first; use a pill only when the strongest free worker cannot manage it, and then pick the weakest worker who can with a pill.

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

  1. Sort both arrays. For a candidate k, take tasks[0 … k-1] and the top k workers.
  2. Walk the chosen tasks from hardest to easiest. If the strongest free worker already qualifies, use them.
  3. Otherwise spend a pill on the weakest free worker who qualifies with it — found by binary search — so stronger workers stay for harder tasks.
  4. 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

Java

private static boolean canAssign(int[] t, int[] w, int pills, int strength, int k) {
    int left = pills;
    List<Integer> avail = new ArrayList<>();
    for (int i = w.length - k; i < w.length; i++) avail.add(w[i]);
    for (int i = k - 1; i >= 0; i--) {
        int need = t[i];
        if (!avail.isEmpty() && avail.get(avail.size() - 1) >= need) {
            avail.remove(avail.size() - 1);
            continue;
        }
        if (left == 0) return false;
        int lo = 0, hi = avail.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if ((long) avail.get(mid) + strength >= need) hi = mid; else lo = mid + 1;
        }
        if (lo == avail.size()) return false;
        avail.remove(lo);
        left--;
    }
    return true;
}

public static int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
    int[] t = tasks.clone();
    int[] w = workers.clone();
    Arrays.sort(t);
    Arrays.sort(w);
    int lo = 0, hi = Math.min(t.length, w.length), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid == 0 || canAssign(t, w, pills, strength, mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

C++

static bool canAssign(vector<int>& t, vector<int>& w, int pills, int strength, int k) {
    int left = pills;
    vector<int> avail(w.end() - k, w.end());
    for (int i = k - 1; i >= 0; i--) {
        int need = t[i];
        if (!avail.empty() && avail.back() >= need) {
            avail.pop_back();
            continue;
        }
        if (left == 0) return false;
        int lo = 0, hi = (int) avail.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((long long) avail[mid] + strength >= need) hi = mid; else lo = mid + 1;
        }
        if (lo == (int) avail.size()) return false;
        avail.erase(avail.begin() + lo);
        left--;
    }
    return true;
}

int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
    vector<int> t = tasks, w = workers;
    sort(t.begin(), t.end());
    sort(w.begin(), w.end());
    int lo = 0, hi = min((int) t.size(), (int) w.size()), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid == 0 || canAssign(t, w, pills, strength, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms