New Problem Solution - "1834. Single-Threaded CPU"

haoel · haoel · commit 738145a27b57 · 2021-04-20T18:24:47.000+08:00
diff --git a/README.md b/README.md
@@ -9,6 +9,7 @@ LeetCode
 
 | # | Title | Solution | Difficulty |
 |---| ----- | -------- | ---------- |
+|1834|[Single-Threaded CPU](https://leetcode.com/problems/single-threaded-cpu/) | [C++](./algorithms/cpp/singleThreadedCpu/SingleThreadedCpu.cpp)|Medium|
 |1833|[Maximum Ice Cream Bars](https://leetcode.com/problems/maximum-ice-cream-bars/) | [C++](./algorithms/cpp/maximumIceCreamBars/MaximumIceCreamBars.cpp)|Medium|
 |1832|[Check if the Sentence Is Pangram](https://leetcode.com/problems/check-if-the-sentence-is-pangram/) | [C++](./algorithms/cpp/checkIfTheSentenceIsPangram/CheckIfTheSentenceIsPangram.cpp)|Easy|
 |1829|[Maximum XOR for Each Query](https://leetcode.com/problems/maximum-xor-for-each-query/) | [C++](./algorithms/cpp/maximumXorForEachQuery/MaximumXorForEachQuery.cpp)|Medium|
diff --git a/algorithms/cpp/singleThreadedCpu/SingleThreadedCpu.cpp b/algorithms/cpp/singleThreadedCpu/SingleThreadedCpu.cpp
@@ -0,0 +1,122 @@
+// Source : https://leetcode.com/problems/single-threaded-cpu/
+// Author : Hao Chen
+// Date   : 2021-04-20
+
+/***************************************************************************************************** 
+ *
+ * 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
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    template<typename T>
+    void print(T q) { 
+        while(!q.empty()) {
+            auto t = q.top();
+            cout << t[2]<< "[" << t[0] <<","<< t[1] << "] ";
+            q.pop();
+        }
+        std::cout << '\n';
+    }
+public:
+    vector<int> getOrder(vector<vector<int>>& tasks) {
+        // push the index into each task.
+        // [enQueueTime, ProcessingTime, index]
+        for(int i=0; i<tasks.size(); i++){
+            tasks[i].push_back(i); 
+        }
+        
+        //Sort the tasks by enQueueTtime
+        sort(tasks.begin(), tasks.end(), [&](vector<int>& lhs, vector<int>& rhs) {
+            return lhs[0] < rhs[0];
+        });
+        
+        //Sort function for tasks priority queue.
+        auto comp = [&](vector<int>& lhs, vector<int>& rhs){
+            // if the processing time is same ,get the smaller index
+            if (lhs[1] == rhs[1]) return lhs[2] > rhs[2]; 
+            // choosing the shorter processing time.
+            return lhs[1] > rhs[1];
+        };
+
+        priority_queue<vector<int>, std::vector<vector<int>>, decltype(comp)> q (comp);
+        vector<int> result;
+        
+        int i = 0;
+        while (i < tasks.size()) {
+            long time = tasks[i][0];
+            int start = i;
+            for (;i < tasks.size() && tasks[start][0] == tasks[i][0];i++ ) {
+                q.push(tasks[i]);
+            }
+            //print(q);
+           
+            while(!q.empty()){
+                //processing the task
+                auto t = q.top(); q.pop();
+                //cout << "DEQUEUE: " <<  t[2] << ":[" << t[0] <<","<< t[1] << "]"<< endl;
+                result.push_back(t[2]);
+                
+                //enQueue the tasks when CPU proceing the current task
+                time += t[1];
+                for(;i < tasks.size() && tasks[i][0] <= time; i++) {
+                    //cout << "ENQUEUE: " <<  tasks[i][2] << ":[" << tasks[i][0] <<","<< tasks[i][1] << "]"<< endl;
+                    q.push(tasks[i]);
+                }
+                //print(q);
+                //cout << endl;
+            }
+        }
+        return result;
+    }
+};
