{"id":8527,"date":"2021-08-08T18:07:18","date_gmt":"2021-08-09T01:07:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8527"},"modified":"2021-08-08T18:08:00","modified_gmt":"2021-08-09T01:08:00","slug":"leetcode-1882-process-tasks-using-servers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1882-process-tasks-using-servers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1882. Process Tasks Using Servers"},"content":{"rendered":"\n

You are given two 0-indexed<\/strong> integer arrays servers<\/code> and tasks<\/code> of lengths n<\/code>\u200b\u200b\u200b\u200b\u200b\u200b and m<\/code>\u200b\u200b\u200b\u200b\u200b\u200b respectively. servers[i]<\/code> is the weight<\/strong> of the i\u200b\u200b\u200b\u200b\u200b\u200bth<\/sup><\/code>\u200b\u200b\u200b\u200b server, and tasks[j]<\/code> is the time needed<\/strong> to process the j\u200b\u200b\u200b\u200b\u200b\u200bth<\/sup><\/code>\u200b\u200b\u200b\u200b task in seconds<\/strong>.<\/p>\n\n\n\n

Tasks are assigned to the servers using a task queue<\/strong>. Initially, all servers are free, and the queue is empty<\/strong>.<\/p>\n\n\n\n

At second j<\/code>, the jth<\/sup><\/code> task is inserted<\/strong> into the queue (starting with the 0th<\/sup><\/code> task being inserted at second 0<\/code>). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight<\/strong>, and in case of a tie, it is assigned to a free server with the smallest index<\/strong>.<\/p>\n\n\n\n

If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion<\/strong> following the weight and index priorities above.<\/p>\n\n\n\n

A server that is assigned task j<\/code> at second t<\/code> will be free again at second t + tasks[j]<\/code>.<\/p>\n\n\n\n

Build an array ans<\/code>\u200b\u200b\u200b\u200b of length m<\/code>, where ans[j]<\/code> is the index<\/strong> of the server the j\u200b\u200b\u200b\u200b\u200b\u200bth<\/sup><\/code> task will be assigned to.<\/p>\n\n\n\n

Return the array <\/em>ans<\/code>\u200b\u200b\u200b\u200b.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> servers = [3,3,2], tasks = [1,2,3,2,1,2]\nOutput:<\/strong> [2,2,0,2,1,2]\nExplanation: <\/strong>Events in chronological order go as follows:\n- At second 0, task 0 is added and processed using server 2 until second 1.\n- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.\n- At second 2, task 2 is added and processed using server 0 until second 5.\n- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.\n- At second 4, task 4 is added and processed using server 1 until second 5.\n- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]\nOutput:<\/strong> [1,4,1,4,1,3,2]\nExplanation: <\/strong>Events in chronological order go as follows: \n- At second 0, task 0 is added and processed using server 1 until second 2.\n- At second 1, task 1 is added and processed using server 4 until second 2.\n- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. \n- At second 3, task 3 is added and processed using server 4 until second 7.\n- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. \n- At second 5, task 5 is added and processed using server 3 until second 7.\n- At second 6, task 6 is added and processed using server 2 until second 7.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • servers.length == n<\/code><\/li>
  • tasks.length == m<\/code><\/li>
  • 1 <= n, m <= 2 * 105<\/sup><\/code><\/li>
  • 1 <= servers[i], tasks[j] <= 2 * 105<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Simulation \/ Priority Queue<\/strong><\/h2>\n\n\n\n
    Two priority queues, one for free servers, another for releasing events.
    One FIFO queue for tasks to schedule.<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector assignTasks(vector& servers, vector& tasks) {\n    const int n = servers.size();\n    const int m = tasks.size();\n    using P = pair;\n    priority_queue, greater
    > frees, release;\n    for (int i = 0; i < n; ++i)\n      frees.emplace(servers[i], i);    \n    vector ans(m);\n    queue q;\n    int l = 0;\n    long t = 0;\n    int count = 0;\n    while (count != m) {      \n      \/\/ Release servers.      \n      while (!release.empty() && release.top().first <= t) {\n        auto [rt, i] = release.top(); release.pop();\n        frees.emplace(servers[i], i);        \n      }\n      \/\/ Enqueue tasks.\n      while (l < m && l <= t) q.push(l++);\n      \/\/ Schedule tasks.\n      while (q.size() && frees.size()) {\n        const int j = q.front(); q.pop();\n        auto [w, i] = frees.top(); frees.pop();\n        release.emplace(t + tasks[j], i);\n        ans[j] = i;\n        ++count;\n      }\n      \/\/ Advance time.\n      if (frees.empty() && !release.empty()) {             \n        t = release.top().first;\n      } else {\n        ++t;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two 0-indexed integer arrays servers and tasks of lengths n\u200b\u200b\u200b\u200b\u200b\u200b and m\u200b\u200b\u200b\u200b\u200b\u200b respectively. servers[i] is the weight of the i\u200b\u200b\u200b\u200b\u200b\u200bth\u200b\u200b\u200b\u200b server, and tasks[j] is the time needed to process the j\u200b\u200b\u200b\u200b\u200b\u200bth\u200b\u200b\u200b\u200b task in seconds. Tasks are assigned to the servers using…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,72,717,179],"class_list":["post-8527","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-priority-queue","tag-schedule","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8527","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8527"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8527\/revisions"}],"predecessor-version":[{"id":8529,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8527\/revisions\/8529"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8527"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8527"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8527"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}