8000 New Problem Solution - "1882. Process Tasks Using Servers" · royeLin/leetcode_cpp@b1e0be8 · GitHub
[go: up one dir, main page]
Skip to content

Commit b1e0be8

Browse files
haoelhaoel
committed
New Problem Solution - "1882. Process Tasks Using Servers"
1 parent 6c839c2 commit b1e0be8

File tree

2 files changed

+120
-0
lines changed

2 files changed

+120
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ LeetCode
99

1010
| # | Title | Solution | Difficulty |
1111
|---| ----- | -------- | ---------- |
12+
|1882|[Process Tasks Using Servers](https://leetcode.com/problems/process-tasks-using-servers/) | [C++](./algorithms/cpp/processTasksUsingServers/ProcessTasksUsingServers.cpp)|Medium|
1213
|1881|[Maximum Value after Insertion](https://leetcode.com/problems/maximum-value-after-insertion/) | [C++](./algorithms/cpp/maximumValueAfterInsertion/MaximumValueAfterInsertion.cpp)|Medium|
1314
|1880|[Check if Word Equals Summation of Two Words](https://leetcode.com/problems/check-if-word-equals-summation-of-two-words/) | [C++](./algorithms/cpp/checkIfWordEqualsSummationOfTwoWords/CheckIfWordEqualsSummationOfTwoWords.cpp)|Easy|
1415
|1871|[Jump Game VII](https://leetcode.com/problems/jump-game-vii/) | [C++](./algorithms/cpp/jumpGame/jumpGame.VII.cpp)|Medium|

‎algorithms/cpp/processTasksUsingServers/ProcessTasksUsingServers.cpp

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
// Source : https://leetcode.com/problems/process-tasks-using-servers/
2+
// Author : Hao Chen
3+
// Date : 2021-05-30
4+
5+
/*****************************************************************************************************
6+
*
7+
* You are given two 0-indexed integer arrays servers and tasks of lengths n and m
8+
* respectively. servers[i] is the weight of the i^th server, and tasks[j] is the time
9+
* needed to process the j^th task in seconds.
10+
*
11+
* You are running a simulation system that will shut down after all tasks are processed. Each server
12+
* can only process one task at a time. You will be able to process the j^th task starting from the
13+
* j^th second beginning with the 0^th task at second 0. To process task j, you assign it to the
14+
* server with the smallest weight that is free, and in case of a tie, choose the server with the
15+
* smallest index. If a free server gets assigned task j at second t, it will be free again at
16+
* the second t + tasks[j].
17+
*
18+
* If there are no free servers, you must wait until one is free and execute the free tasks as soon as
19+
* possible. If multiple tasks need to be assigned, assign them in order of increasing index.
20+
*
21+
* You may assign multiple tasks at the same second if there are multiple free servers.
22+
*
23+
* Build an array ans of length m, where ans[j] is the index of the server the j^th task
24+
* will be assigned to.
25+
*
26+
* Return the array ans.
27+
*
28+
* Example 1:
29+
*
30+
* Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
31+
* Output: [2,2,0,2,1,2]
32+
* Explanation: Events in chronological order go as follows:
33+
* - At second 0, task 0 is added and processed using server 2 until second 1.
34+
* - At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
35+
* - At second 2, task 2 is added and processed using server 0 until second 5.
36+
* - At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
37+
* - At second 4, task 4 is added and processed using server 1 until second 5.
38+
* - At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.
39+
*
40+
* Example 2:
41+
*
42+
* Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
43+
* Output: [1,4,1,4,1,3,2]
44+
* Explanation: Events in chronological order go as follows:
45+
* - At second 0, task 0 is added and processed using server 1 until second 2.
46+
* - At second 1, task 1 is added and processed using server 4 until second 2.
47+
* - At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until
48+
* second 4.
49+
* - At second 3, task 3 is added and processed using server 4 until second 7.
50+
* - At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9.
51+
* - At second 5, task 5 is added and processed using server 3 until second 7.
52+
* - At second 6, task 6 is added and processed using server 2 until second 7.
53+
*
54+
* Constraints:
55+
*
56+
* servers.length == n
57+
* tasks.length == m
58+
* 1 <= n, m <= 2 * 10^5
59+
* 1 <= servers[i], tasks[j] <= 2 * 10^5
60+
******************************************************************************************************/
61+
62+
class Solution {
63+
private:
64+
template<class T>
65+
void print(T q) {
66+
cout << "[";
67+
while(!q.empty()) {
68+
auto& p = q.top();
69+
cout << "[" << p.first << ","<< p.second << "]";
70+
q.pop();
71+
}
72+
cout << "]" << endl;
73+
}
74+
public:
75+
76+
vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
77+
typedef pair<int,int> IntPair;
78+
typedef priority_queue<IntPair, vector<IntPair>, greater<IntPair>> PriorityQueue;
79+
80+
// asc sorted by {weight, index}
81+
PriorityQueue idle;
82+
// asc sorted by {time, index}
83+
PriorityQueue busy;
84+
85+
for(int i=0; i<servers.size(); i++){
86+
idle.push({servers[i], i});
87+
}
88+
89+
//print(idle);
90+
91+
int time = 0;
92+
vector<int> ans;
93+
for(int i=0; i<tasks.size(); i++) {
94+
time = max(i, time);
95+
96+
//check the tasks finished
97+
while(true) {
98+
while(!busy.empty()){
99+
auto& t = busy.top().first;
100+
auto& id = busy.top().second;
101+
if (t > time) break;
102+
idle.push({servers[id], id});
103+
busy.pop();
104+
}
105+
if (!idle.empty()) break;
106+
//set the time to the fisrt finish running task
107+
time = busy.top().first;
108+
}
109+
110+
//process the current task
111+
auto& id = idle.top().second;
112+
ans.push_back(id);
113+
busy.push({time + tasks[i], id});
114+
idle.pop();
115+
}
116+
117+
return ans;
118+
}
119+
};

0 commit comments

Comments
 (0)
0