621. Task Scheduler

Problem Statement

link: LeetCode.cn LeetCode You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there’s a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

Example:

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8

Input: tasks = ["A","C","A","B","D","B"], n = 1 Output: 6

Solution Approach

The algorithm calculates the minimum number of intervals required by determining the maximum frequency of tasks and distributing them with cooling intervals between identical tasks.

Algorithm

1. Calculate Task Frequencies: Use a counter to calculate the frequencies of each task in the input array.
2. Identify Maximum Frequency: Find the task with the maximum frequency and determine how many tasks share this maximum frequency.
3. Calculate Minimum Intervals: Compute the minimum number of intervals required by distributing the tasks with cooling intervals between identical tasks, considering the maximum frequency and the cooling time.

Implement

    class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # counter {A:3,B:2}
        # - - -| - -  - | - - | - - | - -
        # A B    A  B     A 

        counter = collections.Counter(tasks)
        maxx = max(counter.values())
        nmax = len([v for v in counter.values() if v == maxx])
        return max((maxx - 1) * (n + 1) + nmax, len(tasks))

    
    

Twitter  facebook  Email