个人技术分享

Problem: 2071. 你可以安排的最多任务数目

思路

这是一个二分查找和贪心算法的结合问题。我们需要找出可以完成的最大任务数量，这个数量是在任务和工人之间的一个平衡。我们可以使用二分查找来确定这个平衡点，然后使用贪心算法来尽可能地完成更多的任务。

解题方法

我们首先对任务和工人的能力进行排序，然后使用二分查找来确定可以完成的最大任务数量。在每一次二分查找的过程中，我们都会尝试使用当前的中间值作为可能的最大任务数量，然后使用贪心算法来判断是否可以完成这么多的任务。
在贪心算法中，我们会尽可能地让工人在不使用药物的情况下完成任务。如果工人的能力不足以完成任务，我们就会考虑使用药物。我们会优先让能力较弱的工人使用药物，因为他们使用药物后能够带来的能力提升更大。

复杂度

时间复杂度:

$O(n\log n)$，其中 $n$ 是任务的数量。我们需要对任务和工人的能力进行排序，然后进行二分查找。

空间复杂度:

$O(n)$，我们需要使用额外的空间来存储任务和工人的能力。

Code

class Solution {
    static int MAXN = 50001;
    static int[] deque = new int[MAXN];
    static int h, t;
    static int[] tasks;
    static int[] works;

    public int maxTaskAssign(int[] ts, int[] ws, int pills, int strength) {
        tasks = ts;
        works = ws;
        Arrays.sort(works);
        Arrays.sort(tasks);
        int wsize = works.length;
        int tsize = tasks.length;
        int ans = 0, l = 0, r = Math.min(tsize, wsize);
        while (l <= r) {
            int m = (l + r) >> 1;
            if (f(0, m - 1, wsize - m, wsize - 1, strength, pills)) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }

        }
        return ans;
    }

    private static boolean f(int tl, int tr, int wl, int wr, int strength, int pills) {
        h = t = 0;
        int cnts = 0; // 已经使用药的数量
        for (int i = wl, j = tl; i <= wr; i++) {
            // 工人不吃药的情况 去解锁任务
            for (; j <= tr && tasks[j] <= works[i]; j++) {
                deque[t++] = j;
            }
            if (h < t && tasks[deque[h]] <= works[i]) {
                h++;
            } else {
                // 吃药逻辑
                for (; j <= tr && tasks[j] <= works[i] + strength; j++) {
                    deque[t++] = j;
                }
                if (h < t) {
                    cnts++;
                    t--;
                } else {
                    return false;
                }
            }
        }
        return cnts <= pills;
    }
}