2180. Maximum Number Of Tasks You Can Assign¶

Difficulty: Hard

2180. Maximum Number of Tasks You Can Assign

Hard

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⁹

Solution¶

class Solution {
    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        int n = tasks.length;
        int low = 0, high = Math.min(n, workers.length), ans = 0;
        Arrays.sort(tasks);
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, tasks, workers, strength, pills)) {
                ans = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        return ans;
    }

    private boolean ok(int mid, int tasks[], int workers[], int strength, int pills) {
        int n = tasks.length;
        TreeSet<Integer> set = new TreeSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int ele : workers) {
            set.add(ele);
            map.put(ele, map.getOrDefault(ele, 0) + 1);
        }
        for (int i = mid - 1; i >= 0; i--) {
            int current_task = tasks[i];
            if (set.ceiling(current_task) != null) {
                int current_worker = set.ceiling(current_task);
                map.put(current_worker, map.getOrDefault(current_worker, 0) -1);
                if (map.getOrDefault(current_worker, 0) == 0) {
                    map.remove(current_worker);
                    set.remove(current_worker);
                }
            }
            else {
                if (pills == 0) return false;
                if (set.ceiling(current_task - strength) == null) return false;
                pills--;
                int current_worker = set.ceiling(current_task - strength);
                map.put(current_worker, map.getOrDefault(current_worker, 0) -1);
                if (map.getOrDefault(current_worker, 0) == 0) {
                    map.remove(current_worker);
                    set.remove(current_worker);
                }
            }
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here