远程调m有什么任务(m每天必做任务)

2023-07-23：给你 n 个任务和 m 个工人 每个任务需要一定的力量值才能

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)。

package mainimport ( "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))}

在这里插入图片描述

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_tasksrt(); let mut sorted_workers = workers.clone(); sorted_workersrt(); 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_mapsert(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_tasksrt(); let mut sorted_workers = workers.clone(); sorted_workersrt(); 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);}

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

福大大架构师每日一题java当死，golang当立。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。

公众号

福大大架构师每日一题