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., a task cannot be scheduled if the same task was scheduled within the last n units of time). Return 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 needed, can execute all tasks consecutively

Steps

1. Task Frequency: Count the frequency of each task using a map (or hashmap).
2. Max Frequency Task: Identify the task with the maximum frequency. Let's call this maxFreq. This task will determine the lower bound of the execution time.
3. Max Frequency Task Count: Count how many tasks have the maximum frequency. This helps determine potential concurrency.
4. Idle Slots: Calculate the number of idle slots needed. This is based on the maximum frequency task and the cooldown period. Consider that between each max frequency task, there needs to be a gap of n.
5. Total Time: The total time is the sum of the idle slots and the total number of tasks.

Explanation

The key insight is to focus on the most frequent task. This task dictates the minimum time needed. We need to strategically place this task to ensure the cooldown period is respected. Less frequent tasks can fill in the idle slots created by the cooldown. If there are multiple tasks with the maximum frequency, they can be interleaved to minimize idle time.

Code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

    int maxFreq = 0;
    for (auto const& [key, val] : freq) {
        maxFreq = max(maxFreq, val);
    }

    int maxFreqCount = 0;
    for (auto const& [key, val] : freq) {
        if (val == maxFreq) {
            maxFreqCount++;
        }
    }

    long long idleSlots = (long long)(maxFreq - 1) * (n + 1); // n+1 because we need n gaps between maxFreq tasks
    idleSlots -= (maxFreqCount - 1); // subtract extra idle time if we have multiple tasks with maxFreq

    long long totalTime = (long long)tasks.size();
    
    return max((long long)totalTime, idleSlots + totalTime);


}

int main() {
    vector<char> tasks1 = {'A', 'A', 'A', 'B', 'B', 'B'};
    int n1 = 2;
    cout << "Example 1: " << leastInterval(tasks1, n1) << endl; // Output: 8

    vector<char> tasks2 = {'A', 'A', 'A', 'B', 'B', 'B'};
    int n2 = 0;
    cout << "Example 2: " << leastInterval(tasks2, n2) << endl; // Output: 6

    vector<char> tasks3 = {'A','A','A','B','B','B','C','C','C','D','D','E'};
    int n3 = 2;
    cout << "Example 3: " << leastInterval(tasks3, n3) << endl; //Output: 15


    return 0;
}

Complexity

• Time Complexity: O(N), where N is the number of tasks. The frequency counting and the final calculation are linear with respect to the input size.
• Space Complexity: O(1). The map size is bounded by the number of unique tasks (which is at most 26 in the case of uppercase English letters). The space used is constant regardless of the input size.