Skip to main content
Priority Queue

Task Scheduler - LeetCode Daily Challenge

Prerna Sharma

Problem Statement

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, you can do A again as 2 intervals have passed.

Example 2

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Try here before watching the video.

Video Explanation

Java Code

class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for(char task : tasks) {
            frequencyMap.put(task, frequencyMap.getOrDefault(task, 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
        maxHeap.addAll(frequencyMap.entrySet());

        int intervals = 0;

        while(!maxHeap.isEmpty()) {
            int coolDownPeriod = n + 1;
            Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
            while(!maxHeap.isEmpty() && coolDownPeriod > 0) {
                Map.Entry<Character, Integer> entry = maxHeap.poll();
                entry.setValue(entry.getValue() - 1);
                intervals += 1;
                if(entry.getValue() != 0) {       
                    queue.add(entry);
                }
                coolDownPeriod -= 1;
            }

            if(queue.size() != 0) {
                maxHeap.addAll(queue);
                intervals += coolDownPeriod;
            }
        }

        return intervals;
    }
}

C++ Code

class Solution {
public:
    struct comparator {
        bool operator() (pair<char, int> &x, pair<char, int> &y) {
            return y.second > x.second;
        }
    };

    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> frequencyMap;
        for (char task : tasks) {
            frequencyMap[task]++;
        }

        priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> maxHeap;
        for (auto& entry : frequencyMap) {
            maxHeap.push({entry.first, entry.second});
        }

        int intervals = 0;

        while (!maxHeap.empty()) {
            int cooldownPeriod = n + 1;
            queue<pair<char, int>> queue;
            while (!maxHeap.empty() && cooldownPeriod > 0) {
                auto entry = maxHeap.top();
                maxHeap.pop();
                entry.second--;
                intervals++;
                if (entry.second != 0) {
                    queue.push(entry);
                }
                cooldownPeriod--;
            }

            if (!queue.empty()) {
                while (!queue.empty()) {
                    maxHeap.push(queue.front());
                    queue.pop();
                }
                intervals += cooldownPeriod;
            }
        }

        return intervals;
    }
};

Python Code

from collections import Counter
import heapq

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        frequency_map = Counter(tasks)
        max_heap = [(-count, task) for task, count in frequency_map.items()]
        heapq.heapify(max_heap)
        
        intervals = 0
        
        while max_heap:
            cooldown_period = n + 1
            queue = []
            while cooldown_period > 0 and max_heap:
                count, task = heapq.heappop(max_heap)
                count += 1
                intervals += 1
                if count != 0:
                    queue.append((count, task))
                cooldown_period -= 1
                
            if queue:
                intervals += cooldown_period
                for item in queue:
                    heapq.heappush(max_heap, item)
                    
        return intervals

Go Code

type Entry struct {
	task  byte
	count int
}

type MaxHeap []Entry

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i].count > h[j].count }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Entry)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func leastInterval(tasks []byte, n int) int {
	frequencyMap := make(map[byte]int)
	for _, task := range tasks {
		frequencyMap[task]++
	}

	maxHeap := &MaxHeap{}
	for task, count := range frequencyMap {
		heap.Push(maxHeap, Entry{task, count})
	}

	intervals := 0

	for len(*maxHeap) > 0 {
		cooldownPeriod := n + 1
		queue := []Entry{}
		for cooldownPeriod > 0 && len(*maxHeap) > 0 {
			entry := heap.Pop(maxHeap).(Entry)
			entry.count--
			intervals++
			if entry.count > 0 {
				queue = append(queue, entry)
			}
			cooldownPeriod--
		}

		if len(queue) > 0 {
			intervals += cooldownPeriod
			for _, entry := range queue {
				heap.Push(maxHeap, entry)
			}
		}
	}

	return intervals
}

Complexity Analysis

Time Complexity: O(N)
In the worst case, all tasks must be processed, and each task might be inserted and extracted from the priority queue. The priority queue operations (insertion and extraction) have a time complexity of O(log⁡k) each. Therefore, the overall time complexity is O(N * logk). Since k is at maximum 26log⁡k is a constant term. We can simplify the time complexity to O(N). This is a linear time complexity with a high constant factor.
Space Complexity: O(1)
The space complexity is mainly determined by the frequency array and the priority queue. The frequency array has a constant size of 26, and the priority queue can have a maximum size of 26 when all distinct tasks are present. Therefore, the overall space complexity is O(1) or O(26), which is considered constant.