621. Task Scheduler

📝 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 from A-Z input integer n each interval can be idle or allow the completion of a task tasks can be completed in any order constraint: there has to be a gap of at least n 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;
    }
};