# 2071.你可以安排的最多任务数目 (Hard)

## 问题描述
[2071. 你可以安排的最多任务数目 (Hard)](https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/)

给你 `n` 个任务和 `m` 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 **0**
开始的整数数组 `tasks` 中，第 `i` 个任务需要 `tasks[i]`
的力量才能完成。每个工人的力量值保存在下标从 **0** 开始的整数数组 `workers` 中，第 `j`
个工人的力量值为 `workers[j]` 。每个工人只能完成 **一个** 任务，且力量值需要 **大于等于**
该任务的力量要求值（即 `workers[j] >= tasks[i]` ）。

除此以外，你还有 `pills` 个神奇药丸，可以给 **一个工人的力量值** 增加 `strength`
。你可以决定给哪些工人使用药丸，但每个工人 **最多** 只能使用 **一片** 药丸。

给你下标从 **0** 开始的整数数组 `tasks` 和 `workers` 以及两个整数 `pills` 和
`strength` ，请你返回 **最多** 有多少个任务可以被完成。

**示例 1：**

```
输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength =
1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）

```

**示例 2：**

```
输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）

```

**示例 3：**

```
输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3,
strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）

```

**示例 4：**

```
输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1,
strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）

```

**提示：**

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

## 解题思路
二分答案+贪心。

我们假设答案为`ans`，那么一定是前`ans`个消耗精力最小的任务被后`ans`个力量最大的工人完成了。

将工人按力量值从小到大排序，将`task`用`map`来存储，二分答案进行判断时，遍历工人，先与`map.begin()->first`比较，如果大于等于，更新`map`，否则需要吃药，吃药之后必须选择小于等于当前力量的消耗精力最大的任务来处理，如果还是小于`map.bein()->first`，则`return false`，说明`mid > ans`。

建议使用左闭右闭。

## 代码
```cpp
class Solution {
  public:
    bool check(int num, vector<int> &tasks, vector<int> &workers, int pills, map<int, int> mp, int strength) {
        for (int i = 0, j = workers.size() - num; i < tasks.size() && j < workers.size(); ++i, ++j) {
            if (mp.begin()->first > workers[j]) {
                if (pills <= 0) {
                    return false;
                } else {
                    if (mp.begin()->first > strength + workers[j]) {
                        return false;
                    } else {
                        auto iter = mp.lower_bound(strength + workers[j]);
                        if (iter->first == strength + workers[j]) {
                            --iter->second;
                            if (iter->second == 0) {
                                mp.erase(iter);
                            }
                        } else {
                            --iter;
                            --iter->second;
                            if (iter->second == 0) {
                                mp.erase(iter);
                            }
                        }
                        --pills;
                    }
                }
            } else {
                mp.begin()->second--;
                if (mp.begin()->second == 0) {
                    mp.erase(mp.begin());
                }
            }
        }
        return true;
    }
    int maxTaskAssign(vector<int> &tasks, vector<int> &workers, int pills, int strength) {
        // 对工人的力量值从小到大排序
        // 对任务的所需力量值从小到大排序
        // 二分+贪心
        int m = std::min(workers.size(), tasks.size());
        std::sort(tasks.begin(), tasks.end());
        std::sort(workers.begin(), workers.end());
        map<int, int> mp;
        for (int i = 0; i < tasks.size(); i++) {
            mp[tasks[i]]++;
        }
        int left = 0, right = m;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, tasks, workers, pills, mp, strength)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (check(left, tasks, workers, pills, mp, strength))
            return left;
        return left - 1;
    }
};
```