2071. Maximum Number of Tasks You Can Assign

Description

You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the i^th task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the j^th worker having workers[j] strength. Each worker can only be assigned to a single task and must have a strength greater than or equal to the task's strength requirement (i.e., workers[j] >= tasks[i]).

Additionally, you have pills magical pills that will increase a worker's strength by strength. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill.

Given the 0-indexed integer arrays tasks and workers and the integers pills and strength, return the maximum number of tasks that can be completed.

Example 1:

Input: tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
Output: 3
Explanation:
We can assign the magical pill and tasks as follows:
- Give the magical pill to worker 0.
- Assign worker 0 to task 2 (0 + 1 >= 1)
- Assign worker 1 to task 1 (3 >= 2)
- Assign worker 2 to task 0 (3 >= 3)

Example 2:

Input: tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
Output: 1
Explanation:
We can assign the magical pill and tasks as follows:
- Give the magical pill to worker 0.
- Assign worker 0 to task 0 (0 + 5 >= 5)

Example 3:

Input: tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
Output: 2
Explanation:
We can assign the magical pills and tasks as follows:
- Give the magical pill to worker 0 and worker 1.
- Assign worker 0 to task 0 (0 + 10 >= 10)
- Assign worker 1 to task 1 (10 + 10 >= 15)
The last pill is not given because it will not make any worker strong enough for the last task.

Constraints:

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

Solutions

Solution 1: Greedy + Binary Search

Sort the tasks in ascending order of completion time and the workers in ascending order of ability.

Suppose the number of tasks we want to assign is \(x\). We can greedily assign the first \(x\) tasks to the \(x\) workers with the highest strength. If it is possible to complete \(x\) tasks, then it is also possible to complete \(x-1\), \(x-2\), \(x-3\), ..., \(1\), \(0\) tasks. Therefore, we can use binary search to find the maximum \(x\) such that it is possible to complete \(x\) tasks.

We define a function \(check(x)\) to determine whether it is possible to complete \(x\) tasks.

The implementation of \(check(x)\) is as follows:

Iterate through the \(x\) workers with the highest strength in ascending order. Let the current worker being processed be \(j\). The current available tasks must satisfy \(tasks[i] \leq workers[j] + strength\).

If the smallest required strength task \(task[i]\) among the current available tasks is less than or equal to \(workers[j]\), then worker \(j\) can complete task \(task[i]\) without using a pill. Otherwise, the current worker must use a pill. If there are pills remaining, use one pill and complete the task with the highest required strength among the current available tasks. Otherwise, return false.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the number of tasks.

Python3JavaC++GoTypeScript

class Solution:
    def maxTaskAssign(
        self, tasks: List[int], workers: List[int], pills: int, strength: int
    ) -> int:
        def check(x):
            i = 0
            q = deque()
            p = pills
            for j in range(m - x, m):
                while i < x and tasks[i] <= workers[j] + strength:
                    q.append(tasks[i])
                    i += 1
                if not q:
                    return False
                if q[0] <= workers[j]:
                    q.popleft()
                elif p == 0:
                    return False
                else:
                    p -= 1
                    q.pop()
            return True

        n, m = len(tasks), len(workers)
        tasks.sort()
        workers.sort()
        left, right = 0, min(n, m)
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

class Solution {
    private int[] tasks;
    private int[] workers;
    private int strength;
    private int pills;
    private int m;
    private int n;

    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        Arrays.sort(tasks);
        Arrays.sort(workers);
        this.tasks = tasks;
        this.workers = workers;
        this.strength = strength;
        this.pills = pills;
        n = tasks.length;
        m = workers.length;
        int left = 0, right = Math.min(m, n);
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean check(int x) {
        int i = 0;
        Deque<Integer> q = new ArrayDeque<>();
        int p = pills;
        for (int j = m - x; j < m; ++j) {
            while (i < x && tasks[i] <= workers[j] + strength) {
                q.offer(tasks[i++]);
            }
            if (q.isEmpty()) {
                return false;
            }
            if (q.peekFirst() <= workers[j]) {
                q.pollFirst();
            } else if (p == 0) {
                return false;
            } else {
                --p;
                q.pollLast();
            }
        }
        return true;
    }
}

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());
        int n = tasks.size(), m = workers.size();
        int left = 0, right = min(m, n);
        auto check = [&](int x) {
            int p = pills;
            deque<int> q;
            int i = 0;
            for (int j = m - x; j < m; ++j) {
                while (i < x && tasks[i] <= workers[j] + strength) {
                    q.push_back(tasks[i++]);
                }
                if (q.empty()) {
                    return false;
                }
                if (q.front() <= workers[j]) {
                    q.pop_front();
                } else if (p == 0) {
                    return false;
                } else {
                    --p;
                    q.pop_back();
                }
            }
            return true;
        };
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
    sort.Ints(tasks)
    sort.Ints(workers)
    n, m := len(tasks), len(workers)
    left, right := 0, min(m, n)
    check := func(x int) bool {
        p := pills
        q := []int{}
        i := 0
        for j := m - x; j < m; j++ {
            for i < x && tasks[i] <= workers[j]+strength {
                q = append(q, tasks[i])
                i++
            }
            if len(q) == 0 {
                return false
            }
            if q[0] <= workers[j] {
                q = q[1:]
            } else if p == 0 {
                return false
            } else {
                p--
                q = q[:len(q)-1]
            }
        }
        return true
    }
    for left < right {
        mid := (left + right + 1) >> 1
        if check(mid) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

function maxTaskAssign(
    tasks: number[],
    workers: number[],
    pills: number,
    strength: number,
): number {
    tasks.sort((a, b) => a - b);
    workers.sort((a, b) => a - b);

    const n = tasks.length;
    const m = workers.length;

    const check = (x: number): boolean => {
        const dq = new Array<number>(x);
        let head = 0;
        let tail = 0;
        const empty = () => head === tail;
        const pushBack = (val: number) => {
            dq[tail++] = val;
        };
        const popFront = () => {
            head++;
        };
        const popBack = () => {
            tail--;
        };
        const front = () => dq[head];

        let i = 0;
        let p = pills;

        for (let j = m - x; j < m; j++) {
            while (i < x && tasks[i] <= workers[j] + strength) {
                pushBack(tasks[i]);
                i++;
            }

            if (empty()) return false;

            if (front() <= workers[j]) {
                popFront();
            } else {
                if (p === 0) return false;
                p--;
                popBack();
            }
        }
        return true;
    };

    let [left, right] = [0, Math.min(n, m)];
    while (left < right) {
        const mid = (left + right + 1) >> 1;
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

2071. Maximum Number of Tasks You Can Assign

Description

Solutions

Solution 1: Greedy + Binary Search

Comments