2023-07-23：给你 n 个任务和 m 个工人每个任务需要一定的|assign|key|map|下标|算法

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完整代码如下：

packagemain
import(
"fmt"
"sort"
)
funcmaxTaskAssign1(tasks[]int,workers[]int,pillsint,strengthint)int{
l:=0
r:=len(tasks)
varm,ansint
sort.Ints(tasks)
sort.Ints(workers)
forl<=r{
m=(l+r)/2
ifyeah1(tasks,0,m-1,workers,len(workers)-m,len(workers)-1,strength)<=pills{
ans=m
l=m+1
}else{
r=m-1
}
}
returnans
}
funcyeah1(tasks[]int,tlint,trint,workers[]int,wlint,wrint,strengthint)int{
ifwl<0{
returnint(^uint(0)>>1)
}
taskMap:=make(map[int]int)
fori:=tl;i<=tr;i++{
taskMap[tasks[i]]++
}
varansint
fori:=wl;i<=wr;i++{
job:=floorKey(taskMap,workers[i])
ifjob!=nil{
times:=taskMap[*job]
iftimes==1{
delete(taskMap,*job)
}else{
taskMap[*job]--
}
}else{
job=floorKey(taskMap,workers[i]+strength)
ifjob==nil{
returnint(^uint(0)>>1)
}
ans++
times:=taskMap[*job]
iftimes==1{
delete(taskMap,*job)
}else{
taskMap[*job]--
}
}
}
returnans
}
funcfloorKey(taskMapmap[int]int,keyint)*int{
floorKey:=-1
fork:=rangetaskMap{
ifk>floorKey&&k<=key{
floorKey=k
}
}
iffloorKey==-1{
returnnil
}
return&floorKey
}
funcmaxTaskAssign2(tasks[]int,workers[]int,pillsint,strengthint)int{
help:=make([]int,len(tasks))
l:=0
r:=len(tasks)
varm,ansint
sort.Ints(tasks)
sort.Ints(workers)
forl<=r{
m=(l+r)/2
ifyeah2(tasks,0,m-1,workers,len(workers)-m,len(workers)-1,strength,help)<=pills{
ans=m
l=m+1
}else{
r=m-1
}
}
returnans
}
funcyeah2(tasks[]int,tlint,trint,workers[]int,wlint,wrint,strengthint,help[]int)int{
ifwl<0{
returnint(^uint(0)>>1)
}
l:=0
r:=0
ti:=tl
varansint
forwi:=wl;wi<=wr;wi++{
for;ti<=tr&&tasks[ti]<=workers[wi];ti++{
help[r]=ti
r++
}
ifll++
}else{
for;ti<=tr&&tasks[ti]<=workers[wi]+strength;ti++{
help[r]=ti
r++
}
iflans++
r--
}else{
returnint(^uint(0)>>1)
}
}
}
returnans
}
funcmain(){
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完整代码如下：

usestd::collections::BTreeMap;
fnmax_task_assign1(tasks:Vec,workers:Vec,pills:i32,strength:i32)->i32{
letmutl=0;
letmutr=tasks.len();
letmutans=0;
letmutsorted_tasks=tasks.clone();
sorted_tasks.sort();
letmutsorted_workers=workers.clone();
sorted_workers.sort();
whilel<=r{
letm=(l+r)/2;
ifyeah1(
&sorted_tasks,
0,
m-1,
&sorted_workers,
workers.len()-m,
workers.len()-1,
strength,
)<=pills
{
ans=masi32;
l=m+1;
}else{
r=m-1;
}
}
ans
}
fnyeah1(
tasks:&[i32],
tl:usize,
tr:usize,
workers:&[i32],
wl:usize,
wr:usize,
strength:i32,
)->i32{
ifwl>=workers.len(){
returni32::max_value();
}
letmuttask_map=BTreeMap::new();
foriintl..=tr{
*task_map.entry(tasks[i]).or_insert(0)+=1;
}
letmutans=0;
foriinwl..=wr{
letjob=matchtask_map.range(..=workers[i]).rev().next(){
Some((key,_))=>*key,
None=>{
letjob=matchtask_map.range(..=(workers[i]+strength)).rev().next(){
Some((key,_))=>*key,
None=>returni32::max_value(),
};
ans+=1;
job
}
};
lettimes=task_map.get(&job).cloned().unwrap();
iftimes==1{
task_map.remove(&job);
}else{
task_map.insert(job,times-1);
}
}
ans
}
fnmax_task_assign2(tasks:Vec,workers:Vec,pills:i32,strength:i32)->i32{
letmuthelp=vec![0;tasks.len()];
letmutl=0;
letmutr=tasks.len();
letmutans=0;
letmutsorted_tasks=tasks.clone();
sorted_tasks.sort();
letmutsorted_workers=workers.clone();
sorted_workers.sort();
whilel<=r{
letm=(l+r)/2;
ifyeah2(
&sorted_tasks,
0,
m-1,
&sorted_workers,
workers.len()-m,
workers.len()-1,
strength,
&muthelp,
)<=pills
{
ans=masi32;
l=m+1;
}else{
r=m-1;
}
}
ans
}
fnyeah2(
tasks:&[i32],
tl:usize,
tr:usize,
workers:&[i32],
wl:usize,
wr:usize,
strength:i32,
help:&mut[i32],
)->i32{
ifwl>=workers.len(){
returni32::max_value();
}
letmutl=0;
letmutr=0;
letmutti=tl;
letmutans=0;
forwiinwl..=wr{
whileti<=tr&&tasks[ti]<=workers[wi]{
help[r]=tiasi32;
r+=1;
ti+=1;
}
ifll+=1;
}else{
whileti<=tr&&tasks[ti]<=workers[wi]+strength{
help[r]=tiasi32;
r+=1;
ti+=1;
}
iflans+=1;
r-=1;
}else{
returni32::max_value();
}
}
}
ans
}
fnmain(){
lettasks=vec![3,2,1];
letworkers=vec![0,3,3];
letpills=1;
letstrength=1;
letresult1=max_task_assign1(tasks.clone(),workers.clone(),pills,strength);
letresult2=max_task_assign2(tasks,workers,pills,strength);
println!("max_task_assign1result:{}",result1);
println!("max_task_assign2result:{}",result2);
}

c++代码如下：

#include
#include
#include
#include
usingnamespacestd;
intyeah1(vector&tasks,inttl,inttr,vector&workers,intwl,intwr,intstrength){
if(wl<0){
returnINT_MAX;
}
maptaskMap;
for(inti=tl;i<=tr;i++){
taskMap[tasks[i]]++;
}
intans=0;
for(inti=wl;i<=wr;i++){
autojob=taskMap.lower_bound(workers[i]);
if(job!=taskMap.end()){
inttimes=job->second;
if(times==1){
taskMap.erase(job);
}
else{
job->second--;
}
}
else{
job=taskMap.lower_bound(workers[i]+strength);
if(job==taskMap.end()){
returnINT_MAX;
}
ans++;
inttimes=job->second;
if(times==1){
taskMap.erase(job);
}
else{
job->second--;
}
}
}
returnans;
}
intmaxTaskAssign1(vector&tasks,vector&workers,intpills,intstrength){
intl=0;
intr=tasks.size();
intm,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;
}
}
returnans;
}
intyeah2(vector&tasks,inttl,inttr,vector&workers,intwl,intwr,intstrength,vector&help){
if(wl<0){
returnINT_MAX;
}
intl=0;
intr=0;
intti=tl;
intans=0;
for(intwi=wl;wi<=wr;wi++){
for(;ti<=tr&&tasks[ti]<=workers[wi];ti++){
help[r++]=ti;
}
if(ll++;
}
else{
for(;ti<=tr&&tasks[ti]<=workers[wi]+strength;ti++){
help[r++]=ti;
}
if(lans++;
r--;
}
else{
returnINT_MAX;
}
}
}
returnans;
}
intmaxTaskAssign2(vector&tasks,vector&workers,intpills,intstrength){
vectorhelp(tasks.size());
intl=0;
intr=tasks.size();
intm,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;
}
}
returnans;
}
intmain(){
vectortasks={3,2,1};
vectorworkers={0,3,3};
intpills=1;
intstrength=1;
//intresult1=maxTaskAssign1(tasks,workers,pills,strength);
intresult2=maxTaskAssign2(tasks,workers,pills,strength);
//cout<<"ResultfrommaxTaskAssign1:"<cout<<"ResultfrommaxTaskAssign2:"<
return0;
}

c完整代码如下：

#include
#include
intyeah1(int*tasks,inttl,inttr,int*workers,intwl,intwr,intstrength){
if(wl<0){
returnINT_MAX;
}
inttaskMap[1001]={0};
for(inti=tl;i<=tr;i++){
taskMap[tasks[i]]++;
}
intans=0;
for(inti=wl;i<=wr;i++){
intjob=-1;
for(intj=workers[i];j>=0;j--){
if(taskMap[j]>0){
job=j;
break;
}
}
if(job!=-1){
taskMap[job]--;
}
else{
job=-1;
for(intj=workers[i]+strength;j>=workers[i];j--){
if(taskMap[j]>0){
job=j;
break;
}
}
if(job==-1){
returnINT_MAX;
}
ans++;
taskMap[job]--;
}
}
returnans;
}
intcompare(constvoid*a,constvoid*b){
return*(int*)a-*(int*)b;
}
intmaxTaskAssign1(int*tasks,inttasksSize,int*workers,intworkersSize,intpills,intstrength){
intl=0;
intr=tasksSize;
intm,ans=0;
int*sortedTasks=(int*)malloc(tasksSize*sizeof(int));
int*sortedWorkers=(int*)malloc(workersSize*sizeof(int));
for(inti=0;isortedTasks[i]=tasks[i];
}
for(inti=0;isortedWorkers[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);
returnans;
}
intyeah2(int*tasks,inttl,inttr,int*workers,intwl,intwr,intstrength,int*help){
if(wl<0){
returnINT_MAX;
}
intl=0;
intr=0;
intti=tl;
intans=0;
for(intwi=wl;wi<=wr;wi++){
for(;ti<=tr&&tasks[ti]<=workers[wi];ti++){
help[r++]=ti;
}
if(ll++;
}
else{
for(;ti<=tr&&tasks[ti]<=workers[wi]+strength;ti++){
help[r++]=ti;
}
if(lans++;
r--;
}
else{
returnINT_MAX;
}
}
}
returnans;
}
intmaxTaskAssign2(int*tasks,inttasksSize,int*workers,intworkersSize,intpills,intstrength){
int*help=(int*)malloc(tasksSize*sizeof(int));
intl=0;
intr=tasksSize;
intm,ans=0;
int*sortedTasks=(int*)malloc(tasksSize*sizeof(int));
int*sortedWorkers=(int*)malloc(workersSize*sizeof(int));
for(inti=0;isortedTasks[i]=tasks[i];
}
for(inti=0;isortedWorkers[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);
returnans;
}
intmain(){
inttasks[]={3,2,1};
inttasksSize=sizeof(tasks)/sizeof(tasks[0]);
intworkers[]={0,3,3};
intworkersSize=sizeof(workers)/sizeof(workers[0]);
intpills=1;
intstrength=1;
intmax1=maxTaskAssign1(tasks,tasksSize,workers,workersSize,pills,strength);
intmax2=maxTaskAssign2(tasks,tasksSize,workers,workersSize,pills,strength);
printf("maxTaskAssign1:%d\n",max1);
printf("maxTaskAssign2:%d\n",max2);
return0;
}