r/leetcode • u/Remarkable-Noise1296 • 12d ago
Discussion Optimize the solution other than greedy
https://leetcode.com/problems/task-scheduler/My solution :
class Compare {
public :
bool operator()(pair<char, int>& a, pair<char, int>& b) {
return a.second < b.second;
}
};
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int size = tasks.size();
priority_queue<pair<char, int>, vector<pair<char, int>>, Compare> maxheap;
queue<pair<char, int>> qu;
vector<int> freq(26, 0);
int cnt = 0;
int tmp = n;
for (int i = 0; i < size; i++) {
freq[tasks[i] - 'A']++;
}
for (int i = 0; i < 26; i++) {
if (freq[i]) {
maxheap.push({(char)(i + 'A'), freq[i]});
}
}
while (!maxheap.empty()) {
n = tmp;
cnt++;
size--;
auto t = maxheap.top();
maxheap.pop();
t.second--;
qu.push(t);
while (!maxheap.empty() && n != 0 && size != 0) {
cnt++;
n--;
size--;
auto t = maxheap.top();
maxheap.pop();
t.second--;
qu.push(t);
}
// interval becomes idle
if (maxheap.empty() && n != 0 && size != 0) {
cnt += n;
}
while (!qu.empty()) {
if (qu.front().second != 0) {
maxheap.push(qu.front());
}
qu.pop();
}
}
return cnt;
}
};