Maximum Number of Tasks You Can Assign

This question is quite hard to logically understand...

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

complete the tasks from the lowest to highest strength requirement e.g. 0, 1, 5

complete the tasks from the highest to lowest strength requirement e.g. 5, 1, 0

Case #1 (from lowest to highest):

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

normal workers

pilled workers

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:

workers => 1, 2, 8
tasks => 0, 5, 8

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

workers => 1, 2, 6, 8
tasks => 0, 5, 11

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

#1: give pill to worker with strength 2

#2: skip worker with strength 2 and give to worker with strength 8

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:

normal workers

pilled workers

Note, there are 2 cases:

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?!?

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:

e.g. the strongest people will not be attempting the same tasks in [0, 1, 3] when compared to [0, 1, 3, 5, 8] since this strategy involves attempting the strongest tasks first

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.

it also requires me to usually pop elements from the middle of an array which is quite inefficient

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

(I will explain it inside the comments of the code)

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

Time: O(n log (n) + m log (m)) where n is the size of tasks and m is the size of workers

Space: O(min(n + m)) from the deque

learnings

wtf; I did not know sort uses an average of O(log(n)) extra memory on the stack

time taken

28 minutes and 37 seconds