Task Scheduler

XXX. Task Scheduler

Greedy

Array

Problem Statement:

Given a list of tasks represented by letters and a cooldown period n, return the minimum number of units needed to execute all tasks. The same task cannot be executed again before n units have passed.

• Tasks can be executed in any order
• Each task takes 1 unit to execute
• Same task needs n units of cooldown before next execution
• Idle time counts towards total units

Java Solution:

public int leastInterval(char[] tasks, int n) {
    // Count frequency of each task
    int[] count = new int[26];
    
    for (char task : tasks) 
        count[task - 'A']++;
    
    // Sort to get most frequent task at end
    Arrays.sort(count);
    
    // Calculate idle slots based on most frequent task
    int max = count[25] - 1;          // Max number of gaps needed
    int idleSlots = max * n;          // Total idle slots needed
    
    // Fill idle slots with remaining tasks
    for (int i = 0; i <= 24; i++) 
        if (count[i] == count[25])
            idleSlots -= max;          // For tasks with same frequency as max
        else
            idleSlots -= count[i];     // For other tasks
    
    // If idle slots remain, add them to task length
    return idleSlots > 0 ? tasks.length + idleSlots : tasks.length;
}

Example:

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

• Frequency count:
  • A: 3 times
  • B: 3 times
• Calculations:
  • max = 3-1 = 2 (gaps between A's)
  • idleSlots = 2 * 2 = 4 (initial slots)
  • After B fills slots: idleSlots = 0
• Result = 6 (equal to tasks.length)

Complexity:

Time Complexity: O(N), where N is number of tasks
Space Complexity: O(1), fixed size array for count

Implementation Notes:

• **Key Calculations**:
  • max-1 represents required gaps between most frequent task
  • idleSlots = (max-1) * n gives total required idle time
  • Subtract other task occurrences from idle slots
• **Edge Cases**:
  • When all tasks have same frequency
  • When cooldown n = 0
  • When tasks perfectly fill all slots