← leetcode

Process Tasks Using Servers

· Medium

LeetCode problem 1882

you know the one thing i like better than having a schedule? scheduling questions.

that was a joke.

pretty much, you can have two min heaps to track the servers that are not_queued and queued.

  • for not_queued, we will have it ordered based on weight and tie-break on server index
  • for queued, we will have it ordered based on the time it will finish, as well as the weight of the server and its server index

overall, this means for each task:

  • task j can't start before second j, so we move time up to j if it's behind
  • we can check if there are free servers in not_queued to queue tasks with
  • if there aren't, we can simply time-skip to the first instance, where a queued task will finish, and then requeue it with the next task

code link to code

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        vector<int> ans;
        priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> not_queued;
        priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> queued;

        for (int i = 0; i < servers.size(); ++i) {
            not_queued.emplace(servers[i], i);
        }

        long long time = 0;
        for (int j = 0; j < tasks.size(); ++j) {
            int task = tasks[j];
            time = max(time, (long long)j);

            while(!queued.empty() && get<0>(queued.top()) <= time) {
                const auto [_, w, s] = queued.top();
                queued.pop();
                not_queued.emplace(w, s);
            }

            if (!not_queued.empty()) {
                auto [w, s] = not_queued.top();
                not_queued.pop();
                
                queued.emplace(time + task, w, s);
                ans.push_back(s);
            } else {
                const auto [t, w, s] = queued.top();
                queued.pop();
                time = t;

                queued.emplace(time + task, w, s);
                ans.push_back(s);
            }
        }

        return ans;
    }
};

complexity link to complexity

  • Time: O((n + m) log(n)), where n denotes the number of servers that exist and m denotes the number of tasks
  • Space: O(n)

time taken link to time taken

  • 13 minutes and 29 seconds