jobin491's blog

Help with a Leetcode problem
By jobin491, history, 16 months ago, In English

Problem

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

jobin491 Your approach is almost there, but the reason it TLEs is that although you’ve got a $$$\mathcal O(\log N)$$$ outer binary-search, your “check” is in the worst case $$$\mathcal O(K\log N + K\cdot N)$$$ rather than $$$\mathcal O(K\log N)$$$, where $$$K=\min(n,m)$$$. The culprit is how you keep track of which workers are used:

  1. Linear scans on the vector<bool> t

  • You have

    cpp while(j <= m && t[j]) j++;

    to skip used workers, and then later

    cpp while(ind > 0 && t[ind]) ind--;

    to back up from your binary-search result to the nearest unused worker. In the worst case (e.g. many consecutive true’s) each of those can run in $$$\mathcal O(N)$$$. Since you do that for each of up to $$$K$$$ tasks, you can degrade to $$$\mathcal O(K\cdot N)$$$!

  1. vector<bool> specialization
  • vector<bool> is actually a bit-packed proxy type. Every access can be slightly more expensive than a normal vector<char> or vector<uint8_t>. That constant factor can hurt in a tight loop of millions of operations.

Let's see how to fix

You need a data‐structure that gives you:

  • Fast “take largest remaining worker”
  • Fast “find smallest worker ≥ $x$” and erase it

i.e. both in $$$\mathcal O(\log N)$$$. That’s exactly what multiset<int> (or std::multiset) gives you:

multiset<int> S(workers.begin(), workers.end());
…
// take the strongest
auto it = prev(S.end());
if (*it >= tasks[i]) {
  S.erase(it);
} else {
  // try with pill
  auto jt = S.lower_bound(tasks[i] - strength);
  if (jt == S.end()) { flag = false; break; }
  S.erase(jt);
  usedPills++;
}
if (usedPills > p) { flag = false; break; }

This way each assignment is strictly $$$\mathcal O(\log N)$$$, so your total check-function is $$$\mathcal O(K \log N)$$$ and overall $$$\mathcal O(\log N \times K \log N)$$$, which easily fits.

Alternative without multiset

If you really want to avoid multiset, you can also do it with two pointers and a deque:

  1. Sort both tasks and workers in ascending order.
  2. Let’s say you want to check you can do mid tasks.
  3. Push the weakest mid workers into a deque dq.
  4. Iterate i from mid−1 down to 0 over the mid hardest tasks:
  • If dq.back() ≥ tasks[i], pop_back() and assign without pill.
  • Else if dq.front() + strength ≥ tasks[i], pop_front(), use a pill.
  • Else fail.
  1. Track pill usage; if you ever exceed p, fail.

That also gives you $$$\mathcal O(K)$$$ per check (just pushes and pops on the deque), so total $$$\mathcal O(K \log N)$$$.

Concluding

  • Your binary‐search layer is optimal.
  • Your check is slow because you scan a vector<bool> up and down inside the loop.
  • Switch to a true balanced‐BST (multiset) or the two‐pointer + deque trick to get each task‐assignment down to $$$\mathcal O(\log N)$$$ or even $$$\mathcal O(1)$$$, respectively, and you’ll pass within time.
→ Reply