Task Scheduler medium

Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, and an integer n, representing the cooldown period between two same tasks (i.e., the number of units of time that the CPU has to wait before it can run the same task again). You need to find the minimum number of units of time that the CPU will take to finish all the tasks.

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A -> B -> A -> B -> A -> B -> idle -> A

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 Explanation: No cooldown period, so tasks can be executed consecutively.

Steps

1. Task Frequency Counting: Count the frequency of each task using a dictionary or hashmap.
2. Identify the Most Frequent Task: Find the task with the maximum frequency.
3. Calculate Idle Slots: The number of idle slots is determined by the difference between the number of occurrences of the most frequent task and the rest of the tasks. Multiply this difference by n to account for the cooldown periods.
4. Calculate Total Time: The total time is the sum of the number of tasks and the number of idle slots.

Explanation

The key idea is to maximize the usage of idle slots between executions of the most frequent task. We schedule the most frequent task as early as possible and then fill the idle slots (caused by the cooldown) with other tasks. If there are still idle slots left even after utilizing the other tasks, the total time simply includes the total number of tasks.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        // Count task frequencies
        Dictionary<char, int> taskCounts = new Dictionary<char, int>();
        foreach (char task in tasks) {
            taskCounts[task] = taskCounts.GetValueOrDefault(task, 0) + 1;
        }

        // Find the most frequent task
        int maxCount = taskCounts.Values.Max();
        int maxCountTasks = taskCounts.Values.Count(count => count == maxCount);

        //Calculate Idle slots
        int idleSlots = (maxCount - 1) * (n + 1);

        // Calculate total time
        int totalTime = tasks.Length; //Minimum Time
        int remainingTasks = totalTime - maxCountTasks * maxCount; //Tasks that are not the max count tasks
        
        int availableSlots = idleSlots - remainingTasks;
        if(availableSlots > 0)
            totalTime += availableSlots;

        return totalTime;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of tasks. This is because we iterate through the tasks once to count frequencies and then perform constant time operations to calculate the total time.
• Space Complexity: O(1), Assuming a fixed number of possible task types. In the worst case this can be O(N) but is typically considered O(1) for practical input sizes, as the number of unique task types is often small compared to the total number of tasks. If the number of unique tasks is unbounded the space complexity increases to O(M) where M is the number of unique tasks.