algoadvance

Leetcode 621. Task Scheduler Certainly! We’ll go through the solution to the problem “621. Task Scheduler” step-by-step.

Problem Statement

You are given a char array representing tasks that need to be executed. Each task is represented by a character and each task can be done in one unit of time. For each task, there is a cooldown period of n units of time before another identical task can be performed. You need to determine the minimum number of units of time required to complete all tasks.

Example:

  1. Input: tasks = [‘A’,’A’,’A’,’B’,’B’,’B’], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Clarifying Questions

  1. Q: Is there any constraint on the size of the tasks array? A: The length of tasks will be in the range [1, 10,000].

  2. Q: Will the cooldown period n always be a non-negative integer? A: Yes, the cooldown period n is a non-negative integer.

  3. Q: Can we assume uppercase letters only for task identifiers? A: Yes, the tasks are represented by uppercase letters (A-Z).

Strategy

  1. Count Frequencies: Determine the frequency of each task.
  2. Identify Max Frequency: Identify the task with the highest frequency.
  3. Calculate Idle Slots: Use the formula (maxFreq - 1) * n to calculate the initial idle slots needed.
  4. Place Tasks in Idle Slots: Decrease the idle slots as per other task frequencies.
  5. Calculate Minimum Time: The minimum time is either the length of the tasks array (if there are enough tasks to fill idle slots) or the sum of tasks length and remaining idle slots.

Code

import java.util.*;

public class TaskScheduler {
    public int leastInterval(char[] tasks, int n) {
        int[] taskCounts = new int[26];
        
        // Count frequency of each task
        for (char task : tasks) {
            taskCounts[task - 'A']++;
        }
        
        // Sort the task frequencies in descending order
        Arrays.sort(taskCounts);
        int maxFreq = taskCounts[25]; // The most frequent task
        
        // Calculate initially required idle slots
        int idleSlots = (maxFreq - 1) * n;
        
        // Reduce idle slots by placing other tasks
        for (int i = 24; i >= 0 && taskCounts[i] > 0; i--) {
            idleSlots -= Math.min(taskCounts[i], maxFreq - 1);
        }
        
        // If there are idle times left after placing all tasks
        idleSlots = Math.max(0, idleSlots);
        
        return tasks.length + idleSlots;
    }
}

Time Complexity

Thus, the overall time complexity is O(T).

Conclusion

The implemented solution efficiently determines the least time needed to schedule the tasks given the cooldown period. The use of task frequencies and idle slot computation helps ensure that the approach is optimal and adheres to the constraints provided.

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