We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Task Scheduler

Difficulty: Medium

Problem Description

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label. Return the minimum number of CPU intervals required to complete all tasks.

Key Insights

  • The problem requires managing the scheduling of tasks while adhering to a cooldown period between identical tasks.
  • Tasks can be executed in any order, but the placement of tasks with the same label must respect the given cooldown.
  • Idle intervals may be necessary when no tasks can be executed due to the cooldown constraint.
  • The frequency of each task will determine how many idle intervals are needed.

Space and Time Complexity

Time Complexity: O(T + k log k) where T is the number of tasks and k is the number of unique tasks (for sorting). Space Complexity: O(k) for storing the frequency of each unique task.

Solution

To solve the problem, we can use a greedy approach combined with a max heap (or priority queue). The steps are as follows:

  1. Count the frequency of each task using a hash table.
  2. Use a max heap to manage the tasks based on their frequency.
  3. Schedule tasks from the heap, ensuring that each task respects the required cooldown period.
  4. If a task cannot be scheduled due to the cooldown, we need to insert idle intervals until it can be executed again.

This approach effectively minimizes the total number of CPU intervals required.

Code Solutions

from collections import Counter
import heapq

def leastInterval(tasks, n):
    # Count the frequency of each task
    task_count = Counter(tasks)
    # Create a max heap based on task frequency
    max_heap = [-count for count in task_count.values()]
    heapq.heapify(max_heap)
    
    intervals = 0
    
    while max_heap:
        temp = []
        # We can process up to n + 1 tasks (including idle time)
        for i in range(n + 1):
            if max_heap:
                temp.append(heapq.heappop(max_heap))
        
        # Add back the tasks that have remaining counts
        for count in temp:
            if count + 1 < 0:  # if there's still some of this task left
                heapq.heappush(max_heap, count + 1)
        
        # If we processed fewer than n + 1 tasks, we need idle time
        intervals += n + 1 if len(temp) == n + 1 else len(temp)
    
    return intervals
← Back to All Questions