DSA Interview Prep · Lesson

Task Scheduler and Gas Station

Apply greedy reasoning to the CPU task-scheduler cooling period problem and the circular gas-station feasibility problem.

Task Scheduler Problem

Task Scheduler (LeetCode 621): given a list of CPU tasks (each labeled A-Z) and a cooldown n, find the minimum number of CPU intervals to finish all tasks. The same task must wait at least n intervals before running again. Idle intervals are allowed. For tasks ['A','A','A','B','B','B'] with cooldown 2, the answer is 8: A→B→idle→A→B→idle→A→B.

# Task Scheduler example
tasks = ['A','A','A','B','B','B']
n = 2  # cooldown
# One optimal schedule: A B _ A B _ A B
# Intervals: 1 2 3 4 5 6 7 8 → answer = 8

# Another example: tasks=['A','A','A','B','B','C'] n=2
# A B C A B _ A → 7 intervals
print('Understanding the cooldown constraint')
print('Same task needs n intervals gap between runs')

Greedy Formula for Task Scheduler

Key insight: the total time is determined by the most frequent task. If the most frequent task appears f times with count max_count (number of tasks with frequency f), the time is max(len(tasks), (f-1) * (n+1) + max_count). The formula: create f-1 frames of size n+1, fill them with other tasks, and add the last cycle. If other tasks fill all idle slots (many diverse tasks), just execute all tasks with no idle time.

from collections import Counter

def least_interval(tasks, n):
    count = Counter(tasks)
    max_freq = max(count.values())
    # How many tasks have the maximum frequency?
    max_count = sum(1 for c in count.values() if c == max_freq)
    # Formula: max of total tasks (no idle) or frame-based calculation
    frame_time = (max_freq - 1) * (n + 1) + max_count
    return max(len(tasks), frame_time)

print(least_interval(['A','A','A','B','B','B'], 2))  # 8
print(least_interval(['A','A','A','B','B','B'], 0))  # 6 (no cooldown)
print(least_interval(['A','A','A','A','B','C'], 3))  # 10

All lessons in this course

← Back to DSA Interview Prep