问题描述 链接到标题

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

给你 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。

建议使用左闭右闭。

代码 链接到标题 

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;
    }
};