列表

详情

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

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

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { } };

java 解法, 执行用时: 60 ms, 内存消耗: 53.5 MB, 提交时间: 2023-10-08 17:40:44 

class Solution {
    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        //都按从大到小排序
        Arrays.sort(tasks);
        Arrays.sort(workers);
        //最大答案和最小答案
        int min = 0;
        int max = Math.min(tasks.length, workers.length) - 1;
        //二分
        while (min <= max) {
            int mid = (min + max) / 2;
            if (check(tasks, workers, pills, strength, mid)) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return min;
    }

    /**
     * 从下标0到下标mid的任务(最小的mid+1个任务),
     * 是否都能被workers.length - 1 - mid到workers.length - 1下标的工人(力量最大的mid+1个工人)完成
     *
     * @param tasks
     * @param workers
     * @param pills
     * @param strength
     * @param mid
     * @return
     */
    private boolean check(int[] tasks, int[] workers, int pills, int strength, int mid) {
        //工人队列
        Deque<Integer> workerDeque = new ArrayDeque<>();
        int workerIdx = workers.length - 1;
        int workerIdxMin = workers.length - 1 - mid;
        //从大到小遍历任务
        for (int i = mid; i >= 0; i--) {
            while (workerIdx >= workerIdxMin && workers[workerIdx] + strength >= tasks[i]) {
                //从力量最大的工人开始遍历,如果工人吃药丸后,能够完成当前任务,加入队尾
                workerDeque.addLast(workers[workerIdx]);
                workerIdx--;
            }
            if (workerDeque.size() == 0) {
                //没有工人能够完成当前任务
                return false;
            }
            if (workerDeque.getFirst() >= tasks[i]) {
                //队头(队列中,力量最大)的工人可以完成当前任务,让他去完成当前任务.
                workerDeque.removeFirst();
            } else {
                //队头(队列中,力量最大)的工人不能完成当前任务,需要吃药丸
                if (pills == 0) {
                    //没有药丸了
                    return false;
                } else {
                    pills--;
                    //让队里力量最小的工人吃了药丸去完成当前任务.
                    // 因为任务需要的力量是递减的,力量大的工人有可能不吃药丸完成后面的任务
                    workerDeque.removeLast();
                }
            }
        }
        return true;
    }
}

cpp 解法, 执行用时: 276 ms, 内存消耗: 72.5 MB, 提交时间: 2023-10-08 17:39:34 

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        int n = tasks.size(), m = workers.size();
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());
        
        auto check = [&](int mid) -> bool {
            int p = pills;
            deque<int> ws;
            int ptr = m - 1;
            // 从大到小枚举每一个任务
            for (int i = mid - 1; i >= 0; --i) {
                while (ptr >= m - mid && workers[ptr] + strength >= tasks[i]) {
                    ws.push_front(workers[ptr]);
                    --ptr;
                }
                if (ws.empty()) {
                    return false;
                }
                // 如果双端队列中最大的元素大于等于 tasks[i]
                else if (ws.back() >= tasks[i]) {
                    ws.pop_back();
                }
                else {
                    if (!p) {
                        return false;
                    }
                    --p;
                    ws.pop_front();
                }
            }
            return true;
        };
        
        int left = 1, right = min(m, n), ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 948 ms, 内存消耗: 24.6 MB, 提交时间: 2023-10-08 17:39:09 

from sortedcontainers import SortedList

class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        n, m = len(tasks), len(workers)
        tasks.sort()
        workers.sort()

        def check(mid: int) -> bool:
            p = pills
            ws = deque()
            ptr = m - 1
            # 从大到小枚举每一个任务
            for i in range(mid - 1, -1, -1):
                while ptr >= m - mid and workers[ptr] + strength >= tasks[i]:
                    ws.appendleft(workers[ptr])
                    ptr -= 1
                if not ws:
                    return False
                # 如果双端队列中最大的元素大于等于 tasks[i]
                elif ws[-1] >= tasks[i]:
                    ws.pop()
                else:
                    if p == 0:
                        return False
                    p -= 1
                    ws.popleft()
            return True

        left, right, ans = 1, min(m, n), 0
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return ans

python3 解法, 执行用时: 3668 ms, 内存消耗: 25.3 MB, 提交时间: 2023-10-08 17:38:58 

from sortedcontainers import SortedList

class Solution:
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        n, m = len(tasks), len(workers)
        tasks.sort()
        workers.sort()

        def check(mid: int) -> bool:
            p = pills
            #  工人的有序集合
            ws = SortedList(workers[m - mid:])
            # 从大到小枚举每一个任务
            for i in range(mid - 1, -1, -1):
                # 如果有序集合中最大的元素大于等于 tasks[i]
                if ws[-1] >= tasks[i]:
                    ws.pop()
                else:
                    if p == 0:
                        return False
                    rep = ws.bisect_left(tasks[i] - strength)
                    if rep == len(ws):
                        return False
                    p -= 1
                    ws.pop(rep)
            return True

        left, right, ans = 1, min(m, n), 0
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return ans

cpp 解法, 执行用时: 1276 ms, 内存消耗: 275.7 MB, 提交时间: 2023-10-08 17:38:20 

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        int n = tasks.size(), m = workers.size();
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());
        
        auto check = [&](int mid) -> bool {
            int p = pills;
            // 工人的有序集合
            multiset<int> ws;
            for (int i = m - mid; i < m; ++i) {
                ws.insert(workers[i]);
            }
            // 从大到小枚举每一个任务
            for (int i = mid - 1; i >= 0; --i) {
                // 如果有序集合中最大的元素大于等于 tasks[i]
                if (auto it = prev(ws.end()); *it >= tasks[i]) {
                    ws.erase(it);
                }
                else {
                    if (!p) {
                        return false;
                    }
                    auto rep = ws.lower_bound(tasks[i] - strength);
                    if (rep == ws.end()) {
                        return false;
                    }
                    --p;
                    ws.erase(rep);
                }
            }
            return true;
        };
        
        int left = 1, right = min(m, n), ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

golang 解法, 执行用时: 148 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-08 17:37:41 

/**
 * 二分可能完成的任务数k， 此时必然用的是后k大个工人，完成的是前k小个任务
 * 枚举k个工人，把该工人吃药可完成的任务加入todo列表， 如果w[i] >= todo[0], 
 * 则直接完成todo[0] 如果w[i] < todo[0], 则该工人需要吃药，选一个他可完成的最大任务(即todo列表的末尾)
 */
func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {
	sort.Ints(tasks)
	sort.Ints(workers)
	m, n := len(tasks), len(workers)

	return sort.Search(min(m, n)+1, func(k int) bool {
		if k > min(m, n) { // 为了兼容二分查找(Go用的不好想的野路子 Orz)
			return false
		}
		todo, p := []int{}, pills
		idx := 0 // 任务

		for i := n - k; i < n; i++ {
			// 吃药可做任务加入列表
			for ; idx < k && workers[i]+strength >= tasks[idx]; idx++ {
				todo = append(todo, tasks[idx])
			}
			if len(todo) == 0 { // 没有任何任务
				return true
			}
			if workers[i] >= todo[0] { // 不吃药则做最小task
				todo = todo[1:]
			} else { // 吃药则做可做列表最大task
				if p == 0 {
					return true
				}
				todo = todo[:len(todo)-1]
				p--
			}
		}
		return false
	}) - 1
}

// 二分 + 贪心
func maxTaskAssign2(tasks []int, workers []int, pills int, strength int) int {
    n, m := len(tasks), len(workers)
    sort.Ints(tasks)
    sort.Ints(workers)
    check := func(mid int) bool{
        p := pills
        ws := []int{}
        wIndex := m-1
        // 从大到小枚举tasks中的<mid分界线的task
        for tIndex:=mid-1; tIndex>=0; tIndex--{
            // 从大到小枚举 嗑药能完成当前任务的worker
            for wIndex >= m-mid && workers[wIndex] + strength >= tasks[tIndex]{
                // 右进队列
                ws = append(ws, workers[wIndex])
                wIndex--
            }
            if len(ws) == 0{
                return false
            }else if ws[0]>=tasks[tIndex]{
                // 队列左边头是最大的worker，这个worker可以解决当前的task，优先贪心给他
                ws=ws[1:]
            }else{
                // 队列最大的worker不能做这个task，但是队列中嗑药都能解决当前的task，让队列中最小的嗑药解决
                if p == 0{
                    // 药吃完了
                    return false
                }
                p--
                ws = ws[:len(ws)-1]
            }
        }
        // 返回true, 说明可以继续找更多的任务
        return true
    }
    // 二分模板
    l, r, res := 0, min(m, n)+1, 0
    for l+1 != r{
        mid := (l+r)>>1
        if check(mid){
            // 可以接受更多任务，向右收敛
            l = mid
            res = mid
        }else{
            r = mid
        }
        
    }
    
    return res
}

func min(a, b int) int { if a < b { return a }; return b }

上一题

© 2024 leetcode.cn