2071: Maximum-Number-of-Tasks-You-Can-Assign
Hard

This question is quite hard to logically understand…

First, when choosing which tasks to complete, we can either:

Case #1 (from lowest to highest):

There are 2 types of workers you need to account for:

Intuitively speaking, if we are trying to do the lowest strength requirement, for both cases we want to use the lowest strength worker as well.

Unfortunately, the difficulty comes when we are deciding whether to use a normal worker or a pilled worker.

For example, with 1 pill giving strength 3, in test case #1 below:

or an example with 1 pill giving strength 3, in test case #2 below:

You can see that the optimal delegation decision changes drastically between #1 and #2:

With test case #2, there is not an easy way to justify skipping 2, without realising that further down both the workers and tasks array, there exists a task that can be completed only with a pill (no easy greedy solution). Therefore, it might be more feasible to consider the other case…

Case #2 (from highest to lowest):

Similarly, there are 2 types of workers you need to account for:

Note, there are 2 cases:

  1. the strongest worker has more than or equal strength compared to the task with the most strength required
    • e.g. a worker with strength 12 can complete all the tasks: 0, 1, 5, 8
    • logically makes sense to employ them to complete this task
      • they can complete any task; why would they spend all their time on a task that is easier?!?
  2. the strongest worker has less strength compared to the task with the most strength required
    • no-one can complete without the pill; someone needs to consume the pill
    • should try to save our strongest workers
      • why expend our strongest worker with a pill, when we can use a weaker worker and save the stronger worker for tasks down the line that might be possible without needing a pill?

Now, while this does work, our strategy changes depending on how many tasks we are trying to achieve:

Therefore, we can use binary search to check whether completing the k easiest tasks is possible.

Code #1:

class Solution {
public:
    bool completeAssignedTasks (const vector<int>& tasks, vector<int> workers, int pills, int strength, int goal) {
        for (int i = (int)goal-1; i >= 0; --i) {
            if (tasks[i] <= workers.back()) {
                workers.pop_back();
            } else if (pills > 0) {
                bool found = false;
                for (int j = 0; j < (int)workers.size(); ++j) {
                    if (tasks[i] <= workers[j] + strength) {
                        --pills;
                        workers.erase(workers.begin() + j);
                        found = true;
                        break;
                    }
                }
                if (!found) return false;
            } else {
                return false;
            }
        }
        return true;
    }

    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int left = 0, right = min((int) tasks.size(), (int) workers.size());

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (completeAssignedTasks(tasks, workers, pills, strength, middle)) {
                left = middle+1;
            } else {
                right = middle-1;
            }
        }

        return left-1;
    }
};

Originally, I would always iterate from the start of workers to find the worker with the lowest strength to pill.

However, that is quite inefficient, and we can replace this O(n^2) algorithm with an O(n) by using a deque

Code #2:

class Solution {
public:
    bool completeAssignedTasks (const vector<int>& tasks, const vector<int>& workers, int pills, int strength, int goal) {
        int w = workers.size()-1;
        // NOTE: the FRONT will be STRONGEST workers
        // NOTE: the BACK will be WEAKEST workers that can complete tasks with the PILL
        deque<int> dq; 
        for (int i = (int)goal-1; i >= 0; --i) {
            if (!dq.empty() && tasks[i] <= dq.front()) {
                // NOTE: contains the STRONGEST workers
                dq.pop_front();
            } else if (w >= 0 && tasks[i] <= workers[w]) {
                // if `dq` is empty, the STRONGEST workers are still in the `workers` array
                --w;
            } else {
                // while there are workers that still exist,
                // add all the workers that can complete the task with the pill
                while (w >= 0 && tasks[i] <= workers[w] + strength) {
                    dq.push_back(workers[w]);
                    --w;
                }
                // if `dq` is empty, no workers with pill capable of completing the task
                // if `pills == 0`, no pills left for workers
                if (dq.empty() || pills == 0) {
                    return false;
                }
                // the `back` of the `dp` is the most recently added (smallest)
                // will be the worker that consumes the pill to complete the task
                dq.pop_back();
                --pills;
            } 
        }
        return true;
    }

    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int left = 0, right = min((int) tasks.size(), (int) workers.size());

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (completeAssignedTasks(tasks, workers, pills, strength, middle)) {
                left = middle+1;
            } else {
                right = middle-1;
            }
        }

        return left-1;
    }
};

Complexity:

Learnings:

Time Taken: