Editorial: LeetCode 1834 Single Threaded Cpu
https://leetcode.com/problems/single-threaded-cpu/ from Google
Thinking process:
In this problem, we basically need to create a heap, which follows the rules defined in the problem, like the CPU will choose the one with the shortest processing time. Then, we can solve this problem.
There are two things to be noticed. First, we need to fine first task which has the smallest start time. If the start time are the same between two tasks, we pick the one with smallest process time. If the process time are the same between those two tasks, we pick the one with smallest index. So, we need to sort the tasks first, and then add the first task into the heap.
Once we have tasks in our heap, we can pick the task one by one and process them based on the rules. When we process a task, we know when we’re going to be available again. We can use this information and add all the tasks which has a enqueue time earlier than the current finish time into our heap. In this case, our heap doesn’t care about the enqueue time because that’s not in our rules.
Secondly, if we have nothing in our heap but we haven’t finished all tasks, we need to pick another one with the earliest enqueue time. If there are multiple of them, we need to follow the rules. We can do this by picking the task in the order we sort before.
Here is the code.
1class Solution {
2public:
3 typedef unsigned long long ll;
4 vector<int> getOrder(vector<vector<int>>& tasks) {
5 int i = 0;
6 int N = tasks.size();
7 for (auto& t : tasks) {
8 t.push_back(i++);
9 }
10 sort(tasks.begin(), tasks.end(), [](const auto& t1, const auto& t2) {
11 if (t1[0] != t2[0]) return t1[0] < t2[0];
12 else if (t1[1] != t2[1]) return t1[1] < t2[1];
13 else return t1[2] < t2[2];
14 });
15 auto cmp = [](const auto& t1, const auto& t2) {
16 if (t1[1] != t2[1]) return t1[1] > t2[1];
17 else return t1[2] > t2[2];
18 };
19 priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
20 vector<int> ans;
21 pq.push(tasks[0]);
22 i = 1;
23 ll curTime = tasks[0][0];
24 while (pq.size() or i < N) {
25 if (pq.size() == 0) {
26 curTime = tasks[i][0];
27 pq.push(tasks[i++]);
28 }
29 auto t = pq.top(); pq.pop();
30 ans.push_back(t[2]);
31 curTime += t[1];
32 while (i < N and tasks[i][0] <= curTime) {
33 pq.push(tasks[i++]);
34 }
35 }
36 return ans;
37 }
38};