π Problem Details
- Title:
{{problem_title}}
- Link: https://leetcode.com/problems/task-scheduler/
- Difficulty: Medium
- Tags/Categories: Priority-Queue
input array
tasks
tasks[i]
represents a CPU task labeled with a letter fromA-Z
input integern
each interval can beidle
orallow the completion of a task
tasks can be completed in any order constraint: there has to be a gap of at leastn
intervals between two tasks with the same label return the minimum number of intervals required to complete all tasks
πWhat Were My Initial Thoughts?
- each task takes 1 unit of time
- a task must wait for at least n time before being scheduled again
- we can do tasks in any order, which means we should aim to schedule them optimally to minimise idle time
π‘ Explanation of Solution
- use a max-heap priority queue to store task frequencies
- tasks with the highest frequency should be scheduled first to minimise idle time
- use a queue to track cooldowns
- queue keeps track of tasks waiting for their cooldown (n units)
- greedy simulation
- always schedule the most frequent task available
- if a task has been used, put it in cooldown (queue)
- if no tasks are available, insert an idle cycle (time++)
- continue until all tasks are scheduled
β Complexity Analysis
Time Complexity: O(N log 26) β O(N) (N = number of tasks, max 26 unique tasks)
Space Complexity: O(26) β O(1) (Only storing 26 characters)
π» Implementation of Solution
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> freqMap;
// Step 1: Count frequency of each task
for (char task : tasks) {
freqMap[task]++;
}
// Step 2: Use max-heap (priority queue) for most frequent tasks
priority_queue<int> maxHeap;
for (auto& [task, count] : freqMap) {
maxHeap.push(count);
}
// Step 3: Queue to track cooldown tasks {remaining count, time when available}
queue<pair<int, int>> cooldownQueue;
int time = 0;
// Step 4: Process tasks
while (!maxHeap.empty() || !cooldownQueue.empty()) {
time++;
// If a task is available in maxHeap, schedule it
if (!maxHeap.empty()) {
int remaining = maxHeap.top() - 1;
maxHeap.pop();
// If the task still has instances left, push it to cooldown queue
if (remaining > 0) {
cooldownQueue.push({remaining, time + n});
}
}
// If the cooldown period has passed, move task back to heap
if (!cooldownQueue.empty() && cooldownQueue.front().second == time) {
maxHeap.push(cooldownQueue.front().first);
cooldownQueue.pop();
}
}
return time;
}
};