Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example:
Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
- The number of tasks is in the range [1, 10000].
- The integer n is in the range [0, 100].
struct comp {
bool operator()(pair<char, int>& first, pair<char, int>& second) {
return first.second < second.second;
}
};
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int ans = 0;
if (tasks.size() == 0 || n ==0) {
return tasks.size();
}
// Get tasks count in map.
map<char, int> mp;
for (auto task : tasks) {
mp[task]++;
}
priority_queue<pair<char, int>, vector<pair<char, int>>, comp> pq;
// Store the pair info into prioriy queue.
for (auto entry : mp) {
pq.push(entry);
}
while (!pq.empty()) {
vector<pair<char, int>> tasksCompleted;
for (int i = 0; i <= n; i++) {
if (!pq.empty()) {
// This means that a task can be scheduled in this interval.
pair<char, int> entry = pq.top(); pq.pop();
// Decrement the task count list.
entry.second--;
if (entry.second != 0) {
tasksCompleted.push_back(entry);
}
}
// Increment the ans.
ans++;
if (pq.empty() && tasksCompleted.size() == 0) {
return ans;
}
}
// Check if tasks are pending.
for (auto entry : tasksCompleted) {
pq.push(entry);
}
}
return ans;
}
};
========= Next time =====
struct comp {
bool operator()(pair<char, int>& first, pair<char, int>& second) {
return first.second < second.second;
}
};
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
map<char, int> mp;
for (auto task: tasks) {
mp[task]++;
}
priority_queue<pair<char, int>, vector<pair<char, int>>, comp> pq;
for (auto entry : mp) {
pq.push(entry);
}
int ans = 0;
while (!pq.empty()) {
vector<pair<char, int>> remaining_tasks;
for (int i = 0; i <= n; i++) {
if (pq.empty() && remaining_tasks.size() == 0) {
return ans;
}
ans++;
if (pq.empty()) {
continue;
}
pair<char, int> entry = pq.top(); pq.pop();
entry.second--;
if (entry.second > 0) {
remaining_tasks.push_back(entry);
}
}
for (auto task : remaining_tasks) {
pq.push(task);
}
}
return ans;
}
};
=========== Another approach using free slots =====
int leastInterval(vector<char>& tasks, int n) {
int max_freq=0;
vector<int> freq(26,0);
for (char c : tasks)
freq[c-'A']++;
sort(freq.begin(),freq.end());
int free_slots=(freq[25]-1)*n;
for (int i=0; i < 25; i++)
free_slots-=min(freq[25]-1,freq[i]);
return free_slots <= 0 ? tasks.size() : tasks.size()+free_slots;
}
No comments:
Post a Comment