You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the ith task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the jth worker having workers[j] strength. Each worker can only be assigned to a single task and must have a strength greater than or equal to the task's strength requirement (i.e., workers[j] >= tasks[i]). Additionally, you have pills magical pills that will increase a worker's strength by strength. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill. Given the 0-indexed integer arrays tasks and workers and the integers pills and strength, return the maximum number of tasks that can be completed.
below is the code that i tried with a complexity of N(logN)(logN). N=max(n,m); approach: binary search on answer, check the mid smallest tasks: start from the largest task and worker if(task<worker) this worker completes task without pill. if(task>worker) we check for the smallest worker who can complete this task with a pill.
class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int p, int strength) {
int ans = 0;
int n=tasks.size();
int m=workers.size();
sort(workers.rbegin(),workers.rend());
sort(tasks.rbegin(),tasks.rend());
int j=0;
int hi=m;
int lo=0;
int fin=0;
int pills=p;
while(lo<=hi){
int mid= lo+hi;mid/=2;
// check the mid smallest tasks;
pills=p;
if(mid>n){
hi=mid-1;
continue;
}
vector<bool> t(m+1,false);
j=0;
ans=0;
for(int i=n-mid;i<n;i++){
while(j<=m && t[j]) j++;
if(j>=m) break;
if(tasks[i]<=workers[j]){
t[j]=true;
ans++;
}else{
if(strength+workers[j]<tasks[i]){
continue;
}
if(pills>0){
int req= tasks[i]-strength;
int llo=j,lhi=m-1;
int ind=j;
while(llo<=lhi){
int lmid= (llo+lhi)/2;
if(workers[lmid]<req){
lhi=lmid-1;
}else{
ind=lmid;
llo=lmid+1;
}
}
while(ind>0 && t[ind]) ind--;
t[ind]=true;
ans++;
pills--;
}
}
}
if(ans>=mid){
lo=mid+1;
fin=mid;
}else{
hi=mid-1;
}
}
return fin;
}
};
this gives a right answer on all testcases but exceeds time limit. when i checked the correct solution it was with the same complexity using mulitsets
class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int p, int strength) {
int n = tasks.size(), m = workers.size();
// Sorting the tasks and workers in increasing order
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end());
int lo = 0, hi = min(m, n);
int ans;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
int count = 0;
bool flag = true;
// Inserting all workers in a multiset
multiset<int> st(workers.begin(), workers.end());
// Checking if the mid smallest tasks can be assigned
for(int i = mid - 1; i >= 0; i--) {
// Case 1: Trying to assing to a worker without the pill
auto it = prev(st.end());
if(tasks[i] <= *it) {
// Case 1 satisfied!
st.erase(it);
} else {
// Case 2: Trying to assign to a worker with the pill
auto it = st.lower_bound(tasks[i] - strength);
if(it != st.end()) {
// Case 2 satisfied!
count++;
st.erase(it);
} else {
// Case 3: Impossible to assign mid tasks
flag = false;
break;
}
}
// If at any moment, the number of pills require for mid tasks exceeds
// the allotted number of pills, we stop the loop
if(count > p) {
flag = false;
break;
}
}
if(flag) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
};
I am unable to figure out the reason for failure in my code if anyone could help me with it I'd really appreciate it.
