---
tags: leetcode
---

# [1834. Single-Threaded CPU](https://leetcode.com/problems/single-threaded-cpu/)
---
# My Solution
## The Key Idea for Solving This Coding Question
因為題目要求 `tasks[i]` 需在 `enqueueTime_i` 時，才能被 CPU 處理，所以先用排序演算法對 `tasks` 中所有元素依其 enqueueTime 做由小到大的排序。
CPU 會優先處理 processingTime 小的 task。當兩個 task 的 processingTime 相同時， CPU 會優先處理 index 較小的 task。所以我們可以用 heap (priority queue) 對 processingTime 與 index 對已經可以被處理的 task (`currTime >= enqTime`) 進行排序。也就是第 47 ~ 49 行。
第 40 ~ 46 行是在處理當 CPU 沒有工作做時 (即 `heap.empty()` 為 `true`)，將下一個可以被處理的 task 放入 `heap` 中。這裡要注意的是 ==`currTime` 要被更新為 `currTime` 與 `taskList[i].enqTime` 的最大值==。
## C++ Code

struct taskData {
    int id;
    int enqTime;
    int procTime;
    taskData(int id, int enqTime, int procTime) : id(id), enqTime(enqTime), procTime(procTime) {} 
};

bool cmp(taskData &t1, taskData &t2) {
    return t1.enqTime < t2.enqTime;
}

class heapCmp {
public:
    bool operator() (taskData &t1, taskData &t2) {
        if (t1.procTime > t2.procTime) {
            return true;
        } else if (t1.procTime < t2.procTime) {
            return false;
        }
        // t1.procTime == t2.procTime is true.

        return t1.id > t2.id;
    }
};

class Solution {
public:
    vector<int> getOrder(vector<vector<int>> &tasks) {
        vector<taskData> taskList;
        for (int i = 0; i < tasks.size(); ++i) {
            taskList.push_back(taskData(i, tasks[i][0], tasks[i][1]));
        }
        sort(taskList.begin(), taskList.end(), cmp);

        priority_queue<taskData, vector<taskData>, heapCmp> heap;
        unsigned long currTime = taskList[0].enqTime;
        vector<int> processedTasks;
        int i = 0;
        while (!heap.empty() || i < taskList.size()) {
            if (heap.empty()) {
                heap.push(taskList[i]);
                if (currTime < taskList[i].enqTime) {
                    currTime = taskList[i].enqTime;
                }
                ++i;
            }
            while (i < taskList.size() && taskList[i].enqTime <= currTime) {
                heap.push(taskList[i++]);
            }

            currTime += heap.top().procTime;
            processedTasks.push_back(heap.top().id);
            heap.pop();
        }

        return processedTasks;
    }
};

## Time Complexity
$O(nlogn)$
$n$ is the length of `tasks`.
## Space Complexity
$O(n)$
# Miscellaneous
<!--
# Test Cases

[[1,2],[2,4],[3,2],[4,1]]

[[7,10],[7,12],[7,5],[7,4],[7,2]]

* Runtime Error:
https://leetcode.com/submissions/detail/565931450/testcase/
* Wrong Answer

[[1,2],[2,4],[3,2],[3,2],[3,2],[4,1]]

-->