Task Scheduler

Schedule tasks with cooling period using greedy approach with heap

Language Selection

Choose your preferred programming language

Showing: Python

Task Scheduler

Problem Statement

Given a characters array tasks representing tasks to do. Each task is represented by a capital letter. Tasks could be done without the original order of the array. Each task is done in one unit of time. For each unit of time, you could complete either one task or just be idle.

However, there is a non-negative integer n representing the cooling time between two same tasks (the same letter in the array), that is, there must be at least n units of time between any two same tasks.

Return the least number of units of time the CPU will be busy (including idle time).

Input/Output Specifications

  • Input:
    • tasks: Array of characters representing tasks
    • n: Integer representing cooling period between same tasks
  • Output: Integer representing minimum time units needed

Constraints

  • 1 <= task.length <= 10^4
  • tasks[i] is upper-case English letter
  • 0 <= n <= 100

Examples

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B
One possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: No cooling needed, so tasks can run continuously.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: One possible sequence: A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Solution Approaches

Approach 1: Max-Heap with Greedy Strategy (Optimal)

Algorithm Explanation:

  1. Count frequency of each task
  2. Use max-heap to always pick task with highest frequency
  3. For each time cycle of length n+1:
    • Pick up to n+1 different tasks (highest frequency first)
    • If fewer than n+1 tasks available, add idle time
    • Decrease frequency and put back in heap if frequency > 0
  4. Continue until all tasks completed

Implementation:

Python:

import heapq
from collections import Counter

def least_interval(tasks, n):
    """
    Task scheduler using max-heap and greedy strategy
    Time: O(n log k) where k is unique tasks
    Space: O(k)
    """
    if n == 0:
        return len(tasks)
    
    # Count task frequencies
    count = Counter(tasks)
    
    # Max-heap (use negative frequencies)
    max_heap = [-freq for freq in count.values()]
    heapq.heapify(max_heap)
    
    time = 0
    
    while max_heap:
        cycle = []
        
        # Process up to n+1 tasks in current cycle
        for _ in range(n + 1):
            if max_heap:
                freq = heapq.heappop(max_heap)
                if freq < -1:  # Still has remaining tasks
                    cycle.append(freq + 1)  # Decrease frequency
        
        # Put back tasks with remaining frequency
        for freq in cycle:
            heapq.heappush(max_heap, freq)
        
        # Add time for this cycle
        if max_heap:
            time += n + 1  # Full cycle
        else:
            time += len(cycle)  # Partial cycle (last one)
    
    return time

# Alternative cleaner implementation
def least_interval_v2(tasks, n):
    """
    Cleaner implementation with explicit idle calculation
    Time: O(n log k)
    Space: O(k)
    """
    count = Counter(tasks)
    max_heap = [-freq for freq in count.values()]
    heapq.heapify(max_heap)
    
    time = 0
    
    while max_heap:
        temp = []
        cycle_count = 0
        
        # Execute tasks for one complete cycle
        for _ in range(n + 1):
            if max_heap:
                freq = -heapq.heappop(max_heap)
                cycle_count += 1
                if freq > 1:
                    temp.append(freq - 1)
        
        # Put back remaining tasks
        for freq in temp:
            heapq.heappush(max_heap, -freq)
        
        # Calculate time for this cycle
        if max_heap:  # More tasks remaining
            time += n + 1
        else:  # Last cycle
            time += cycle_count
    
    return time

Java:

import java.util.*;

class Solution {
    /**
     * Task scheduler using max-heap and greedy strategy
     * Time: O(n log k) where k is unique tasks
     * Space: O(k)
     */
    public int leastInterval(char[] tasks, int n) {
        if (n == 0) return tasks.length;
        
        // Count task frequencies
        Map<Character, Integer> count = new HashMap<>();
        for (char task : tasks) {
            count.put(task, count.getOrDefault(task, 0) + 1);
        }
        
        // Max-heap for frequencies
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(count.values());
        
        int time = 0;
        
        while (!maxHeap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int cycleCount = 0;
            
            // Process one complete cycle
            for (int i = 0; i <= n; i++) {
                if (!maxHeap.isEmpty()) {
                    int freq = maxHeap.poll();
                    cycleCount++;
                    if (freq > 1) {
                        temp.add(freq - 1);
                    }
                }
            }
            
            // Put back remaining tasks
            maxHeap.addAll(temp);
            
            // Calculate time for this cycle
            if (maxHeap.isEmpty()) {
                time += cycleCount; // Last cycle
            } else {
                time += n + 1; // Full cycle
            }
        }
        
        return time;
    }
}

Go:

import (
    "container/heap"
)

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
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.(int))
}

func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// leastInterval - Task scheduler using max-heap
// Time: O(n log k), Space: O(k)
func leastInterval(tasks []byte, n int) int {
    if n == 0 {
        return len(tasks)
    }
    
    // Count task frequencies
    count := make(map[byte]int)
    for _, task := range tasks {
        count[task]++
    }
    
    // Build max-heap
    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    
    for _, freq := range count {
        heap.Push(maxHeap, freq)
    }
    
    time := 0
    
    for maxHeap.Len() > 0 {
        var temp []int
        cycleCount := 0
        
        // Process one complete cycle
        for i := 0; i <= n && maxHeap.Len() > 0; i++ {
            freq := heap.Pop(maxHeap).(int)
            cycleCount++
            if freq > 1 {
                temp = append(temp, freq-1)
            }
        }
        
        // Put back remaining tasks
        for _, freq := range temp {
            heap.Push(maxHeap, freq)
        }
        
        // Calculate time for this cycle
        if maxHeap.Len() == 0 {
            time += cycleCount // Last cycle
        } else {
            time += n + 1 // Full cycle
        }
    }
    
    return time
}

Approach 2: Mathematical Formula (Most Efficient)

Algorithm Explanation:

  1. Find task with maximum frequency
  2. Calculate minimum time based on most frequent task
  3. Use formula: max(total_tasks, (max_freq - 1) * (n + 1) + count_max_freq)

Implementation:

Python:

def least_interval_math(tasks, n):
    """
    Task scheduler using mathematical formula
    Time: O(n) where n is number of tasks
    Space: O(1)
    """
    from collections import Counter
    
    count = Counter(tasks)
    max_freq = max(count.values())
    max_count = sum(1 for freq in count.values() if freq == max_freq)
    
    # Minimum time is either:
    # 1. Total tasks (if no cooling needed)
    # 2. Time slots created by most frequent task + other max frequency tasks
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Key Insights

  • Greedy Strategy: Always execute task with highest frequency when possible
  • Cycle-based Thinking: Process tasks in cycles of length n+1
  • Mathematical Optimization: Can solve with formula based on max frequency
  • Idle Time Calculation: Fill gaps with other tasks before adding idle time

Edge Cases

  1. n = 0: No cooling period, return total tasks
  2. Single Task Type: Maximum idle time scenario
  3. All Different Tasks: No cooling needed
  4. Perfect Distribution: Tasks fit exactly without idle time

Test Cases

def test_least_interval():
    # Example 1
    assert least_interval(["A","A","A","B","B","B"], 2) == 8
    
    # No cooling needed
    assert least_interval(["A","A","A","B","B","B"], 0) == 6
    
    # Single task type
    assert least_interval(["A","A","A"], 2) == 7
    
    # All different tasks
    assert least_interval(["A","B","C","D"], 2) == 4
    
    # Test mathematical approach
    assert least_interval_math(["A","A","A","B","B","B"], 2) == 8
    assert least_interval_math(["A","A","A","A","A","A","B","C","D","E","F","G"], 2) == 16
    
    print("All tests passed!")

test_least_interval()

Interview Tips

  1. Recognize Greedy Pattern: Always choose most frequent available task
  2. Cycle Visualization: Draw timeline to show cooling periods
  3. Mathematical Insight: Explain optimal formula derivation
  4. Edge Cases: Handle n=0 and single task type scenarios
  5. Alternative Approaches: Mention both heap and mathematical solutions

Follow-up Questions

  1. Different Cooling Times: Each task type has different cooling period
  2. Priority Tasks: Some tasks have higher priority
  3. Resource Constraints: Limited number of CPUs
  4. Dynamic Tasks: Tasks arrive continuously
  5. Minimize Idle Time: Different optimization objective

Common Mistakes

  1. Wrong Cycle Length: Using n instead of n+1 for cycle size
  2. Heap Management: Incorrectly handling frequency updates
  3. Edge Case: Not handling n=0 case properly
  4. Last Cycle: Not accounting for partial last cycle correctly
  5. Mathematical Formula: Incorrect derivation of optimal formula

Concept Explanations

Greedy Cooling Strategy: The key insight is that we should always execute the task with the highest remaining frequency (when allowed by cooling constraints) to minimize overall completion time.

Cycle-Based Scheduling: By thinking in cycles of length n+1, we ensure that any task executed at the beginning of a cycle can be safely executed again at the beginning of the next cycle.

Mathematical Optimization: The optimal time is determined by the most frequent task, which creates a “skeleton” of time slots. Other tasks fill the gaps, and only if gaps can’t be filled do we need idle time.

When to Apply: Use this pattern for scheduling problems with constraints, resource allocation with cooldowns, or any problem where you need to optimally sequence operations with dependencies or restrictions.