1834. Single-Threaded CPU

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Sorting、Heap (Priority Queue>

一、題目

You are given n​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the i​​​​​​th​​​​ task will be available to process at enqueueTimei and will take processingTimei to finish processing.
You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

  • If the CPU is idle and there are no available tasks to process, the CPU remains idle.
  • If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
  • Once a task is started, the CPU will process the entire task without stopping.
  • The CPU can finish a task then start a new one instantly. Return the order in which the CPU will process the tasks.

Example 1:

  • Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
  • Output: [0,2,3,1]
  • Explanation: The events go as follows:
  • At time = 1, task 0 is available to process. Available tasks = {0}.
  • Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
  • At time = 2, task 1 is available to process. Available tasks = {1}.
  • At time = 3, task 2 is available to process. Available tasks = {1, 2}.
  • Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
  • At time = 4, task 3 is available to process. Available tasks = {1, 3}.
  • At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
  • At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
  • At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

  • Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
  • Output: [4,3,2,0,1]
  • Explanation: The events go as follows:
  • At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
  • Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
  • At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
  • At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
  • At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
  • At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
  • At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

  • tasks.length == n
  • 1 <= n <= 10^5
  • 1 <= enqueueTimei, processingTimei <= 10^9

二、分析

  • 執行緒排程問題，直覺會將所有的 task 排序後，依據時間從 0 走到最後來處理這個問題，但是當秒數很大時，就會浪費很多時間，所以我們應該注意的時每個 trigger point，也就是新的 task 任務加入與結束的時候。
  • 討論兩個情況，
    1. 當 Thread 是閒置時，直接跳到最前面的 task(即 trigger point 是任務加入時)。
    2. 當 Thread 不是閒置時，會將當下的 task 執行完後，所以得到結束的時間後，一次將符合 enqueueTime 的 task 加入佇列(即 trigger point 是任務結束時)。
  • 由於這裡會優先處理 processingTime 較短的，所以在這裡可以用 min heap 來處理。
  • 需注意，在排序前需先標記索引值。
  • 需注意，timestamp 可能是大數。

三、解題

1. Heap (Priority Queue)

  • Time complexity: \(O(n\log n)\)
  • Space complexity: \(O(n)\)
vector<int> getOrder(vector<vector<int>>& tasks) {
    auto comp = [](const auto& a, const auto& b){return a.first == b.first ? a.second > b.second : a.first > b.first;};
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(comp)> pq(comp);  // min heap
    long long int timestamp = 0;
    int n = tasks.size();
    vector<int> res; 
    for (int i = 0; i < tasks.size(); i++) {
        tasks[i].push_back(i);      // 標記索引值
    }
    sort(tasks.begin(), tasks.end());   // 排序
    int i = 0;
    while (res.size() < n) {
        if (pq.empty()) {               // 閒置時，時間標籤移動到佇列最前面的任務
            timestamp = tasks[i][0];
        } else {                        // 非閒置時，將時間標籤移動到任務結束時
            auto top = pq.top();
            timestamp += top.first;
            res.push_back(top.second);
            pq.pop();
        }
        while (i < n && tasks[i][0] <= timestamp) { // 加入所有比時間標籤早的任務
            pq.push({tasks[i][1], tasks[i][2]});    // 以 {processingTime, index} 的方式加入 min heap
            i++;
        }
    }   
    return res;
}

回目錄 Catalog