2023-07-23：给你 n 个任务和 m 个工人每个任务需要一定的力量值才能完成需要的力量值保存在下标从 0 开始的整数数组 tasks 中第 i 个任务需要 tasks[i] 的力量才能完

作者：福大大架构师每日一题

2023-07-23
北京
本文字数：8184 字
阅读完需：约 27 分钟

2023-07-23：给你 n 个任务和 m 个工人

每个任务需要一定的力量值才能完成

需要的力量值保存在下标从 0 开始的整数数组 tasks 中

第 i 个任务需要 tasks[i] 的力量才能完成

每个工人的力量值保存在下标从 0 开始的整数数组 workers 中

第 j 个工人的力量值为 workers[j]

每个工人只能完成一个任务

且力量值需要大于等于该任务的力量要求值, 即 workers[j] >= tasks[i]

除此以外，你还有 pills 个神奇药丸

可以给一个工人的力量值增加 strength

你可以决定给哪些工人使用药丸

但每个工人最多只能使用一片药丸。

给你下标从 0 开始的整数数组 tasks 和 workers 以及

两个整数 pills 和 strength ，请你返回最多有多少个任务可以被完成。

来自华为。

输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1。

输出：3。

答案 2023-07-23：

maxTaskAssign1:

1.对任务数组 tasks 和工人数组 workers 进行升序排序。

2.使用二分查找在任务数组 tasks 中找到一个索引 m，使得从 tasks[0] 到 tasks[m-1] 的任务可以被 workers[len(workers)-m] 到 workers[len(workers)-1] 完成。

3.判断使用药丸后，从 tasks[m] 到 tasks[len(tasks)-1] 的剩余任务是否能够被剩余的工人完成。

4.如果可以完成，则继续在右半部分寻找更大的 m 值；如果无法完成，则在左半部分寻找更小的 m 值。

5.返回最终的 m 值，即最多可以完成的任务数。

maxTaskAssign2:

1.对任务数组 tasks 和工人数组 workers 进行升序排序。

2.使用二分查找在任务数组 tasks 中找到一个索引 m，使得从 tasks[0] 到 tasks[m-1] 的任务可以被 workers[len(workers)-m] 到 workers[len(workers)-1] 完成。

3.使用辅助数组 help 存储满足条件的任务索引。

4.从 workers[wl] 到 workers[wr] 遍历每个工人，依次分配任务。

5.在任务数组 tasks 中，使用双指针 l 和 r，将满足 workers[wi] <= tasks[help[l]] <= workers[wi]+strength 的任务指针存入 help 数组。

6.如果 l < r，则说明有任务可以被工人完成，将任务数加一，并将 r 减一。

7.如果 l >= r，则说明无法完成任务，返回一个很大的值。

8.返回最终的任务数。

算法 maxTaskAssign1 的时间复杂度为 O(n log n + m log m)，空间复杂度为 O(n + m)。

算法 maxTaskAssign2 的时间复杂度为 O((n + m) log n)，空间复杂度为 O(n)。

go 完整代码如下：

package main
import (    "fmt"    "sort")
func maxTaskAssign1(tasks []int, workers []int, pills int, strength int) int {    l := 0    r := len(tasks)    var m, ans int    sort.Ints(tasks)    sort.Ints(workers)    for l <= r {        m = (l + r) / 2        if yeah1(tasks, 0, m-1, workers, len(workers)-m, len(workers)-1, strength) <= pills {            ans = m            l = m + 1        } else {            r = m - 1        }    }    return ans}
func yeah1(tasks []int, tl int, tr int, workers []int, wl int, wr int, strength int) int {    if wl < 0 {        return int(^uint(0) >> 1)    }    taskMap := make(map[int]int)    for i := tl; i <= tr; i++ {        taskMap[tasks[i]]++    }    var ans int    for i := wl; i <= wr; i++ {        job := floorKey(taskMap, workers[i])        if job != nil {            times := taskMap[*job]            if times == 1 {                delete(taskMap, *job)            } else {                taskMap[*job]--            }        } else {            job = floorKey(taskMap, workers[i]+strength)            if job == nil {                return int(^uint(0) >> 1)            }            ans++            times := taskMap[*job]            if times == 1 {                delete(taskMap, *job)            } else {                taskMap[*job]--            }        }    }    return ans}
func floorKey(taskMap map[int]int, key int) *int {    floorKey := -1    for k := range taskMap {        if k > floorKey && k <= key {            floorKey = k        }    }    if floorKey == -1 {        return nil    }    return &floorKey}
func maxTaskAssign2(tasks []int, workers []int, pills int, strength int) int {    help := make([]int, len(tasks))    l := 0    r := len(tasks)    var m, ans int    sort.Ints(tasks)    sort.Ints(workers)    for l <= r {        m = (l + r) / 2        if yeah2(tasks, 0, m-1, workers, len(workers)-m, len(workers)-1, strength, help) <= pills {            ans = m            l = m + 1        } else {            r = m - 1        }    }    return ans}
func yeah2(tasks []int, tl int, tr int, workers []int, wl int, wr int, strength int, help []int) int {    if wl < 0 {        return int(^uint(0) >> 1)    }    l := 0    r := 0    ti := tl    var ans int    for wi := wl; wi <= wr; wi++ {        for ; ti <= tr && tasks[ti] <= workers[wi]; ti++ {            help[r] = ti            r++        }        if l < r && tasks[help[l]] <= workers[wi] {            l++        } else {            for ; ti <= tr && tasks[ti] <= workers[wi]+strength; ti++ {                help[r] = ti                r++            }            if l < r {                ans++                r--            } else {                return int(^uint(0) >> 1)            }        }    }    return ans}
func main() {    tasks := []int{3, 2, 1}    workers := []int{0, 3, 3}    pills := 1    strength := 1
    fmt.Println("maxTaskAssign1:", maxTaskAssign1(tasks, workers, pills, strength))    fmt.Println("maxTaskAssign2:", maxTaskAssign2(tasks, workers, pills, strength))}

复制代码

rust 完整代码如下：

use std::collections::BTreeMap;
fn max_task_assign1(tasks: Vec<i32>, workers: Vec<i32>, pills: i32, strength: i32) -> i32 {    let mut l = 0;    let mut r = tasks.len();    let mut ans = 0;    let mut sorted_tasks = tasks.clone();    sorted_tasks.sort();    let mut sorted_workers = workers.clone();    sorted_workers.sort();
    while l <= r {        let m = (l + r) / 2;        if yeah1(            &sorted_tasks,            0,            m - 1,            &sorted_workers,            workers.len() - m,            workers.len() - 1,            strength,        ) <= pills        {            ans = m as i32;            l = m + 1;        } else {            r = m - 1;        }    }
    ans}
fn yeah1(    tasks: &[i32],    tl: usize,    tr: usize,    workers: &[i32],    wl: usize,    wr: usize,    strength: i32,) -> i32 {    if wl >= workers.len() {        return i32::max_value();    }
    let mut task_map = BTreeMap::new();    for i in tl..=tr {        *task_map.entry(tasks[i]).or_insert(0) += 1;    }
    let mut ans = 0;    for i in wl..=wr {        let job = match task_map.range(..=workers[i]).rev().next() {            Some((key, _)) => *key,            None => {                let job = match task_map.range(..=(workers[i] + strength)).rev().next() {                    Some((key, _)) => *key,                    None => return i32::max_value(),                };                ans += 1;                job            }        };        let times = task_map.get(&job).cloned().unwrap();        if times == 1 {            task_map.remove(&job);        } else {            task_map.insert(job, times - 1);        }    }
    ans}
fn max_task_assign2(tasks: Vec<i32>, workers: Vec<i32>, pills: i32, strength: i32) -> i32 {    let mut help = vec![0; tasks.len()];    let mut l = 0;    let mut r = tasks.len();    let mut ans = 0;    let mut sorted_tasks = tasks.clone();    sorted_tasks.sort();    let mut sorted_workers = workers.clone();    sorted_workers.sort();
    while l <= r {        let m = (l + r) / 2;        if yeah2(            &sorted_tasks,            0,            m - 1,            &sorted_workers,            workers.len() - m,            workers.len() - 1,            strength,            &mut help,        ) <= pills        {            ans = m as i32;            l = m + 1;        } else {            r = m - 1;        }    }
    ans}
fn yeah2(    tasks: &[i32],    tl: usize,    tr: usize,    workers: &[i32],    wl: usize,    wr: usize,    strength: i32,    help: &mut [i32],) -> i32 {    if wl >= workers.len() {        return i32::max_value();    }
    let mut l = 0;    let mut r = 0;    let mut ti = tl;    let mut ans = 0;
    for wi in wl..=wr {        while ti <= tr && tasks[ti] <= workers[wi] {            help[r] = ti as i32;            r += 1;            ti += 1;        }
        if l < r && tasks[help[l as usize] as usize] <= workers[wi] {            l += 1;        } else {            while ti <= tr && tasks[ti] <= workers[wi] + strength {                help[r] = ti as i32;                r += 1;                ti += 1;            }
            if l < r {                ans += 1;                r -= 1;            } else {                return i32::max_value();            }        }    }
    ans}
fn main() {    let tasks = vec![3, 2, 1];    let workers = vec![0, 3, 3];    let pills = 1;    let strength = 1;
    let result1 = max_task_assign1(tasks.clone(), workers.clone(), pills, strength);    let result2 = max_task_assign2(tasks, workers, pills, strength);
    println!("max_task_assign1 result: {}", result1);    println!("max_task_assign2 result: {}", result2);}

复制代码

c++代码如下：

#include <iostream>#include <vector>#include <algorithm>#include <map>
using namespace std;
int yeah1(vector<int>& tasks, int tl, int tr, vector<int>& workers, int wl, int wr, int strength) {    if (wl < 0) {        return INT_MAX;    }    map<int, int> taskMap;    for (int i = tl; i <= tr; i++) {        taskMap[tasks[i]]++;    }    int ans = 0;    for (int i = wl; i <= wr; i++) {        auto job = taskMap.lower_bound(workers[i]);        if (job != taskMap.end()) {            int times = job->second;            if (times == 1) {                taskMap.erase(job);            }            else {                job->second--;            }        }        else {            job = taskMap.lower_bound(workers[i] + strength);            if (job == taskMap.end()) {                return INT_MAX;            }            ans++;            int times = job->second;            if (times == 1) {                taskMap.erase(job);            }            else {                job->second--;            }        }    }    return ans;}
int maxTaskAssign1(vector<int>& tasks, vector<int>& workers, int pills, int strength) {    int l = 0;    int r = tasks.size();    int m, ans = 0;    sort(tasks.begin(), tasks.end());    sort(workers.begin(), workers.end());    while (l <= r) {        m = (l + r) / 2;        if (yeah1(tasks, 0, m - 1, workers, workers.size() - m, workers.size() - 1, strength) <= pills) {            ans = m;            l = m + 1;        }        else {            r = m - 1;        }    }    return ans;}
int yeah2(vector<int>& tasks, int tl, int tr, vector<int>& workers, int wl, int wr, int strength, vector<int>& help) {    if (wl < 0) {        return INT_MAX;    }    int l = 0;    int r = 0;    int ti = tl;    int ans = 0;    for (int wi = wl; wi <= wr; wi++) {        for (; ti <= tr && tasks[ti] <= workers[wi]; ti++) {            help[r++] = ti;        }        if (l < r && tasks[help[l]] <= workers[wi]) {            l++;        }        else {            for (; ti <= tr && tasks[ti] <= workers[wi] + strength; ti++) {                help[r++] = ti;            }            if (l < r) {                ans++;                r--;            }            else {                return INT_MAX;            }        }    }    return ans;}
int maxTaskAssign2(vector<int>& tasks, vector<int>& workers, int pills, int strength) {    vector<int> help(tasks.size());    int l = 0;    int r = tasks.size();    int m, ans = 0;    sort(tasks.begin(), tasks.end());    sort(workers.begin(), workers.end());    while (l <= r) {        m = (l + r) / 2;        if (yeah2(tasks, 0, m - 1, workers, workers.size() - m, workers.size() - 1, strength, help) <= pills) {            ans = m;            l = m + 1;        }        else {            r = m - 1;        }    }    return ans;}
int main() {    vector<int> tasks = { 3, 2, 1 };    vector<int> workers = { 0, 3, 3 };    int pills = 1;    int strength = 1;
    //int result1 = maxTaskAssign1(tasks, workers, pills, strength);    int result2 = maxTaskAssign2(tasks, workers, pills, strength);
    //cout << "Result from maxTaskAssign1: " << result1 << endl;    cout << "Result from maxTaskAssign2: " << result2 << endl;
    return 0;}

复制代码

c 完整代码如下：

#include <stdio.h>#include <stdlib.h>
int yeah1(int* tasks, int tl, int tr, int* workers, int wl, int wr, int strength) {    if (wl < 0) {        return INT_MAX;    }    int taskMap[1001] = { 0 };
    for (int i = tl; i <= tr; i++) {        taskMap[tasks[i]]++;    }
    int ans = 0;
    for (int i = wl; i <= wr; i++) {        int job = -1;
        for (int j = workers[i]; j >= 0; j--) {            if (taskMap[j] > 0) {                job = j;                break;            }        }
        if (job != -1) {            taskMap[job]--;        }        else {            job = -1;
            for (int j = workers[i] + strength; j >= workers[i]; j--) {                if (taskMap[j] > 0) {                    job = j;                    break;                }            }
            if (job == -1) {                return INT_MAX;            }
            ans++;            taskMap[job]--;        }    }
    return ans;}
int compare(const void* a, const void* b) {    return *(int*)a - *(int*)b;}
int maxTaskAssign1(int* tasks, int tasksSize, int* workers, int workersSize, int pills, int strength) {    int l = 0;    int r = tasksSize;    int m, ans = 0;    int* sortedTasks = (int*)malloc(tasksSize * sizeof(int));    int* sortedWorkers = (int*)malloc(workersSize * sizeof(int));
    for (int i = 0; i < tasksSize; i++) {        sortedTasks[i] = tasks[i];    }
    for (int i = 0; i < workersSize; i++) {        sortedWorkers[i] = workers[i];    }
    qsort(sortedTasks, tasksSize, sizeof(int), compare);    qsort(sortedWorkers, workersSize, sizeof(int), compare);
    while (l <= r) {        m = (l + r) / 2;
        if (yeah1(sortedTasks, 0, m - 1, sortedWorkers, workersSize - m, workersSize - 1, strength) <= pills) {            ans = m;            l = m + 1;        }        else {            r = m - 1;        }    }
    free(sortedTasks);    free(sortedWorkers);
    return ans;}
int yeah2(int* tasks, int tl, int tr, int* workers, int wl, int wr, int strength, int* help) {    if (wl < 0) {        return INT_MAX;    }
    int l = 0;    int r = 0;    int ti = tl;    int ans = 0;
    for (int wi = wl; wi <= wr; wi++) {        for (; ti <= tr && tasks[ti] <= workers[wi]; ti++) {            help[r++] = ti;        }
        if (l < r && tasks[help[l]] <= workers[wi]) {            l++;        }        else {            for (; ti <= tr && tasks[ti] <= workers[wi] + strength; ti++) {                help[r++] = ti;            }
            if (l < r) {                ans++;                r--;            }            else {                return INT_MAX;            }        }    }
    return ans;}
int maxTaskAssign2(int* tasks, int tasksSize, int* workers, int workersSize, int pills, int strength) {    int* help = (int*)malloc(tasksSize * sizeof(int));    int l = 0;    int r = tasksSize;    int m, ans = 0;    int* sortedTasks = (int*)malloc(tasksSize * sizeof(int));    int* sortedWorkers = (int*)malloc(workersSize * sizeof(int));
    for (int i = 0; i < tasksSize; i++) {        sortedTasks[i] = tasks[i];    }
    for (int i = 0; i < workersSize; i++) {        sortedWorkers[i] = workers[i];    }
    qsort(sortedTasks, tasksSize, sizeof(int), compare);    qsort(sortedWorkers, workersSize, sizeof(int), compare);
    while (l <= r) {        m = (l + r) / 2;
        if (yeah2(sortedTasks, 0, m - 1, sortedWorkers, workersSize - m, workersSize - 1, strength, help) <= pills) {            ans = m;            l = m + 1;        }        else {            r = m - 1;        }    }
    free(help);    free(sortedTasks);    free(sortedWorkers);
    return ans;}
int main() {    int tasks[] = { 3, 2, 1 };    int tasksSize = sizeof(tasks) / sizeof(tasks[0]);    int workers[] = { 0, 3, 3 };    int workersSize = sizeof(workers) / sizeof(workers[0]);    int pills = 1;    int strength = 1;
    int max1 = maxTaskAssign1(tasks, tasksSize, workers, workersSize, pills, strength);    int max2 = maxTaskAssign2(tasks, tasksSize, workers, workersSize, pills, strength);
    printf("maxTaskAssign1: %d\n", max1);    printf("maxTaskAssign2: %d\n", max2);
    return 0;}