2023-07-23：給你 n 個(gè)任務(wù)和 m 個(gè)工人 每個(gè)任務(wù)需要一定的力量值才能完成 需要的力量
2023-07-23：給你 n 個(gè)任務(wù)和 m 個(gè)工人
每個(gè)任務(wù)需要一定的力量值才能完成
需要的力量值保存在下標(biāo)從 0 開始的整數(shù)數(shù)組 tasks 中
第 i 個(gè)任務(wù)需要 tasks[i] 的力量才能完成
每個(gè)工人的力量值保存在下標(biāo)從 0 開始的整數(shù)數(shù)組 workers 中
第 j 個(gè)工人的力量值為 workers[j]
每個(gè)工人只能完成 一個(gè) 任務(wù)
且力量值需要 大于等于 該任務(wù)的力量要求值, 即 workers[j] >= tasks[i]
除此以外，你還有 pills 個(gè)神奇藥丸
可以給 一個(gè)工人的力量值 增加 strength
你可以決定給哪些工人使用藥丸
但每個(gè)工人 最多 只能使用 一片 藥丸。
給你下標(biāo)從 0 開始的整數(shù)數(shù)組tasks 和 workers 以及
兩個(gè)整數(shù) pills 和 strength ，請(qǐng)你返回 最多 有多少個(gè)任務(wù)可以被完成。
來自華為。
輸入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1。
輸出：3。
答案2023-07-23：
maxTaskAssign1:
1.對(duì)任務(wù)數(shù)組 tasks 和工人數(shù)組 workers 進(jìn)行升序排序。
2.使用二分查找在任務(wù)數(shù)組 tasks 中找到一個(gè)索引 m，使得從 tasks[0] 到 tasks[m-1] 的任務(wù)可以被 workers[len(workers)-m] 到 workers[len(workers)-1] 完成。
3.判斷使用藥丸后，從 tasks[m] 到 tasks[len(tasks)-1] 的剩余任務(wù)是否能夠被剩余的工人完成。
4.如果可以完成，則繼續(xù)在右半部分尋找更大的 m 值；如果無法完成，則在左半部分尋找更小的 m 值。
5.返回最終的 m 值，即最多可以完成的任務(wù)數(shù)。
maxTaskAssign2:
1.對(duì)任務(wù)數(shù)組 tasks 和工人數(shù)組 workers 進(jìn)行升序排序。
2.使用二分查找在任務(wù)數(shù)組 tasks 中找到一個(gè)索引 m，使得從 tasks[0] 到 tasks[m-1] 的任務(wù)可以被 workers[len(workers)-m] 到 workers[len(workers)-1] 完成。
3.使用輔助數(shù)組 help 存儲(chǔ)滿足條件的任務(wù)索引。
4.從 workers[wl] 到 workers[wr] 遍歷每個(gè)工人，依次分配任務(wù)。
5.在任務(wù)數(shù)組 tasks 中，使用雙指針 l 和 r，將滿足 workers[wi] <= tasks[help[l]] <= workers[wi]+strength 的任務(wù)指針存入 help 數(shù)組。
6.如果 l < r，則說明有任務(wù)可以被工人完成，將任務(wù)數(shù)加一，并將 r 減一。
7.如果 l >= r，則說明無法完成任務(wù)，返回一個(gè)很大的值。
8.返回最終的任務(wù)數(shù)。
算法maxTaskAssign1的時(shí)間復(fù)雜度為O(n log n + m log m)，空間復(fù)雜度為O(n + m)。
算法maxTaskAssign2的時(shí)間復(fù)雜度為O((n + m) log n)，空間復(fù)雜度為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++代碼如下：
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完整代碼如下：
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;
}
