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

举报
福大大架构师每日一题 发表于 2023/07/23 21:48:34 2023/07/23
【摘要】 2023-07-23:给你 n 个任务和 m 个工人每个任务需要一定的力量值才能完成需要的力量值保存在下标从 0 开始的整数数组 tasks 中第 i 个任务需要 tasks[i] 的力量才能完成每个工人的力量值保存在下标从 0 开始的整数数组 workers 中第 j 个工人的力量值为 workers[j]每个工人只能完成 一个 任务且力量值需要 大于等于 该任务的力量要求值, 即 wor...

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

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。