algoadvance

Leetcode 621. Task Scheduler

Problem Statement

A CPU has n tasks labeled from A to Z. Given an array of characters tasks, where each character represents a task, the tasks could be done without any order. Each task could be completed in one interval. For each interval, the CPU could complete one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (i.e., there must be at least n intervals between two same tasks while the CPU is processing other tasks or being idle).

Given the array tasks and the integer n, return the least number of intervals the CPU will take to finish all the given tasks.

Clarifying Questions

  1. Input Constraints:
    • The number of tasks is in the range [1, 10^4].
    • tasks consists of upper case English letters.
    • The integer n is in the range [0, 100].
  2. Output:
    • Return a single integer representing the minimum intervals needed.

Strategy

To determine the least number of intervals to finish all given tasks, while respecting the cooldown periods, we can use the following strategy:

  1. Determine the Frequency of Tasks:
    • Calculate the frequency of each task using an array where the index represents each letter from A to Z.
  2. Sort the Frequencies:
    • Sort the frequencies in descending order to handle the most frequent tasks first.
  3. Calculate the Minimum Intervals:
    • Use the maximum frequency to calculate the number of full cycles needed to complete the tasks. A cycle can be visualized as the most frequent task followed by n slots until it can be executed again.
    • Calculate the number of idle slots based on the number of full cycles and the remaining tasks.
    • Fill in the idle slots with remaining tasks to minimize idle intervals.
  4. Compare Total Intervals:
    • The result is the total intervals which are the sum of task slots and any remaining idle slots.

Time Complexity

Code

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        // Frequency array for tasks 'A' to 'Z'
        vector<int> freq(26, 0);
        
        // Count frequency of each task
        for(char task : tasks) {
            freq[task - 'A']++;
        }
        
        // Sort the frequencies in descending order
        sort(freq.begin(), freq.end(), greater<int>());
        
        // maxFreq is the highest frequency of any task
        int maxFreq = freq[0];
        // Idle spots count: (maxFreq - 1) * n
        int idleSpots = (maxFreq - 1) * n;
        
        // Reduce idle spots with the most frequent tasks
        for(int i = 1; i < 26; i++) {
            if (freq[i] == 0) break; // No more tasks
            idleSpots -= min(maxFreq - 1, freq[i]);
        }
        
        // If we have negative idle spots, it means tasks can be scheduled without need of idle time.
        idleSpots = max(0, idleSpots);
        
        // Total length is tasks + idle spots
        return tasks.size() + idleSpots;
    }
};

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI