LeetCode 621: Task Scheduler Solution in Python – A Step-by-Step Guide

What Is LeetCode 621: Task Scheduler?

In LeetCode 621: Task Scheduler, you’re given a list of tasks (characters, e.g., ["A","A","B"]) and an integer n representing the cooldown period between identical tasks. Your task is to find the minimum time (slots) needed to complete all tasks, allowing idle slots when necessary. For example, with tasks ["A","A","B"] and n = 2, you can’t do "A" then "A" without 2 slots between, so one schedule is "A B idle A" (4 slots). This problem tests your ability to optimize sequences with constraints.

Problem Statement

• Input:
• tasks: A list of characters (e.g., ["A","A","B"]).
• n: Integer cooldown period (≥ 0).
• Output: An integer—the least number of time slots to complete all tasks.
• Rules:
• Same task requires n slots between executions.
• Different tasks can run consecutively.
• Insert idle slots if needed.

Constraints

• 1 ≤ tasks.length ≤ 10⁴.
• Tasks are uppercase letters (A-Z).
• 0 ≤ n ≤ 100.

Examples

• Input: tasks = ["A","A","B"], n = 2
• Output: 4 (e.g., "A B idle A")
• Input: tasks = ["A","A","A","B","B","B"], n = 2
• Output: 8 (e.g., "A B idle A B idle A B")
• Input: tasks = ["A","B","C"], n = 1
• Output: 3 (e.g., "A B C")

These examples show the scheduling—let’s solve it!

Understanding the Problem: Scheduling with Cooldown

To solve LeetCode 621: Task Scheduler in Python, we need to arrange tasks to minimize time slots, respecting the cooldown n between identical tasks. A naive approach might simulate each slot, but we can optimize with frequency analysis or simulation. We’ll use:

• Best Solution (Greedy with Frequency Counting): O(n) time, O(1) space—fast and elegant (n = tasks length).
• Alternative Solution (Priority Queue Simulation): O(n log k) time, O(k) space—k is unique tasks—dynamic but complex.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Frequency Counting

Why This Is the Best Solution

The greedy frequency counting approach is the top choice for LeetCode 621 because it’s efficient—O(n) time with O(1) space—and uses a mathematical insight: the minimum time is driven by the most frequent task, padded by cooldowns, and filled with other tasks or idle slots. It avoids simulation, making it scalable (≤ 10⁴ tasks). It’s like planning with the busiest task first and fitting others around it!

How It Works

Think of this as a task planner:

• Step 1: Count Frequencies:
• Tally each task’s occurrences (e.g., A:2, B:1).
• Step 2: Find Max Frequency:
• Identify the most frequent task(s) and their count.
• Step 3: Calculate Base Time:
• Formula: (max_freq - 1) * (n + 1) + num_max_tasks.
• (max_freq - 1): Full cooldown cycles.
• (n + 1): Task plus cooldown slots.
• num_max_tasks: Tasks with max frequency in last cycle.
• Step 4: Compare with Total Tasks:
• Return max of base time and total tasks (if more tasks fill idle slots).
• Step 5: Return Result:
• Output the minimum slots.

It’s like a scheduler’s blueprint—count and compute!

Step-by-Step Example

Example: tasks = ["A","A","B"], n = 2

• Step 1: Frequencies: {A: 2, B: 1}.
• Step 2: Max freq = 2 (A), num_max_tasks = 1 (only A).
• Step 3: Base time:
• (2 - 1) (2 + 1) + 1 = 1 3 + 1 = 4.
• "A _ _ A" (B fits in gaps).
• Step 4: Total tasks = 3, max(4, 3) = 4.
• Output: 4.

Example: tasks = ["A","A","A","B","B","B"], n = 2

• Step 1: {A: 3, B: 3}.
• Step 2: Max freq = 3, num_max_tasks = 2 (A and B).
• Step 3: (3 - 1) (2 + 1) + 2 = 2 3 + 2 = 8.
• "A B _ A B _ A B".
• Step 4: Total = 6, max(8, 6) = 8.
• Output: 8.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Step 1: Count frequencies
        freq = Counter(tasks)

        # Step 2: Find max frequency and count of max tasks
        max_freq = max(freq.values())
        num_max_tasks = sum(1 for count in freq.values() if count == max_freq)

        # Step 3: Calculate base time with cooldown
        base_time = (max_freq - 1) * (n + 1) + num_max_tasks

        # Step 4: Compare with total tasks
        total_tasks = len(tasks)
        min_slots = max(base_time, total_tasks)

        # Step 5: Return result
        return min_slots

• Line 1: Import Counter for frequency counting.
• Line 6: Count task frequencies.
• Lines 9-10: Find max frequency and count of tasks with that frequency.
• Line 13: Compute base time with formula.
• Lines 16-17: Ensure result ≥ total tasks.
• Time Complexity: O(n)—counting and max operations.
• Space Complexity: O(1)—fixed 26 letters.

This is like a task optimizer—quick and clever!

Alternative Solution: Priority Queue Simulation

Why an Alternative Approach?

The priority queue simulation uses a max heap to schedule tasks dynamically—O(n log k) time, O(k) space (k = unique tasks). It’s more intuitive, mimicking real scheduling, but slower due to heap operations. It’s like running a live task queue with cooldowns!

How It Works

Picture this as a task queue:

• Step 1: Count frequencies into a max heap.
• Step 2: Simulate time slots:
• Pop up to n+1 tasks, process, track cooldowns.
• Push back tasks after cooldown.
• Step 3: Count total slots.
• Step 4: Return result.

It’s like a real-time scheduler—step-by-step!

Step-by-Step Example

Example: tasks = ["A","A","B"], n = 2

• Step 1: Heap: [-2(A), -1(B)].
• Step 2: Simulate:
• Slot 0: Pop A (-1 left), slots=1.
• Slot 1: Pop B (0 left), slots=2.
• Slot 2: Idle, push A (-1) after cooldown, slots=3.
• Slot 3: Pop A (0 left), slots=4.
• Output: 4.

Code for Priority Queue Approach

Copy codefrom collections import Counter
from heapq import heappush, heappop

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Step 1: Count frequencies and build max heap
        freq = Counter(tasks)
        heap = [-count for count in freq.values()]
        heapify(heap)

        # Step 2: Simulate scheduling
        slots = 0
        while heap:
            cycle = []  # Tasks to process in this cycle
            for _ in range(n + 1):  # Up to n+1 slots
                if heap:
                    count = heappop(heap)
                    if count < -1:  # More instances remain
                        cycle.append(count + 1)
            # Push back tasks after cooldown
            for count in cycle:
                heappush(heap, count)
            # Increment slots: full cycle if heap remains, else just used slots
            slots += n + 1 if heap else len(cycle)

        # Step 3: Return total slots
        return slots

• Lines 6-9: Build max heap of negative counts.
• Lines 12-23: Simulate:
• Process up to n+1 tasks per cycle.
• Track slots with idle time.
• Time Complexity: O(n log k)—heap operations.
• Space Complexity: O(k)—heap size (k ≤ 26).

It’s a task simulator—dynamic but complex!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n) time, O(1) space, fast and elegant.
• Cons: Less intuitive.
• Priority Queue (Alternative):
• Pros: O(n log k) time, O(k) space, mimics scheduling.
• Cons: Slower, more code.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• Input: ["A"], n = 0
• Output: 1.
• Input: ["A","A"], n = 1
• Output: 3 (A _ A).

Both handle these well.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Priority Queue: Time O(n log k), Space O(k).

Greedy is optimal.

Key Takeaways

• Greedy: Frequency math—smart!
• Priority Queue: Real simulation—clear!
• Scheduling: Constraints are fun.
• Python Tip: Counters rock—see Python Basics.

Final Thoughts: Schedule Those Tasks

LeetCode 621: Task Scheduler in Python is a cool optimization challenge. Greedy frequency counting offers speed and elegance, while priority queues provide a dynamic view. Want more? Try LeetCode 56: Merge Intervals or LeetCode 767: Reorganize String. Ready to plan? Head to Solve LeetCode 621 on LeetCode and schedule those tasks today!