-
Notifications
You must be signed in to change notification settings - Fork 3
/
621.cpp
34 lines (32 loc) · 919 Bytes
/
621.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef pair<int, char> P;
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> task2cnt;
for (auto c : tasks) task2cnt[c]++;
priority_queue<P> pq;
for (auto& element : task2cnt) {
pq.push({element.second, element.first});
}
int totalTime = 0;
int cycle = n + 1;
while (!pq.empty()) {
int time = 0;
vector<P> v;
for (int i = 0; i < cycle; ++i) {
if (!pq.empty()) {
v.push_back(pq.top());
pq.pop();
time++;
}
}
for (auto p : v) {
if (--p.first) {
pq.push(p);
}
}
totalTime += !pq.empty() ? cycle : time;
}
return totalTime;
}
};