Task SchedulerとGas Station

Task Scheduler 問題

# 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')

Task Scheduler の貪欲法の公式

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

この公式が成り立つ理由

# Visualise frame structure for AAABBB, n=2
# Frame size = n+1 = 3
# f = 3 (A appears 3 times), max_count = 2 (A and B both appear 3 times)
# Grid:
# [A B _]  ← frame 1
# [A B _]  ← frame 2  
# [A B  ]  ← last partial frame (max_count=2 cells)
# Total = (3-1)*3 + 2 = 6 + 2 = 8

# If tasks = AAAABBCC, n=2: max_freq=4 (A), max_count=1
# (4-1)*(2+1)+1 = 9+1 = 10
# But len(tasks)=8 < 10, so answer is 10
tasks2 = ['A','A','A','A','B','B','C','C']
from collections import Counter
count = Counter(tasks2)
mf = max(count.values())
mc = sum(1 for c in count.values() if c == mf)
print(f'Frame formula: ({mf}-1)*{2+1}+{mc} = {(mf-1)*(2+1)+mc}')
print(f'Max(len={len(tasks2)}, frame={max(len(tasks2),(mf-1)*3+mc)}) = {max(len(tasks2),(mf-1)*3+mc)}')

ヒープによるシミュレーションの別解

import heapq
from collections import deque, Counter

def task_scheduler_simulate(tasks, n):
    count = Counter(tasks)
    heap = [-c for c in count.values()]  # max-heap using negation
    heapq.heapify(heap)
    time = 0
    cooldown = deque()  # (available_at, neg_count)
    while heap or cooldown:
        time += 1
        if heap:
            c = heapq.heappop(heap) + 1  # use one instance
            if c < 0:  # still has remaining tasks
                cooldown.append((time + n, c))
        if cooldown and cooldown[0][0] == time:
            heapq.heappush(heap, cooldown.popleft()[1])
    return time

print(task_scheduler_simulate(['A','A','A','B','B','B'], 2))  # 8

Gas Station 問題

# Example:
gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
# net gain per station: gas[i] - cost[i]
net = [g - c for g, c in zip(gas, cost)]
print('Net gain per station:', net)  # [-2, -2, -2, 3, 3]
# Only possible start: station 3 (index 3)
# Tank: 0 +3=3 → 3-1=2 → 2+1=3-2=... let's verify
print('Sum of net:', sum(net))  # 1 > 0 means solution exists

Gas Station の貪欲解法

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1  # impossible
    tank = 0
    start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            tank = 0
            start = i + 1  # current start failed, try next
    return start

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(can_complete_circuit(gas, cost))  # 3

gas2  = [2, 3, 4]
cost2 = [3, 4, 3]
print(can_complete_circuit(gas2, cost2))  # -1

貪欲法で出発地点を選べる理由

# Proof sketch: why start=i+1 is correct after tank<0 at station i
# If we start at station j (start <= j <= i), tank at j is tank_from_start(j)
# After stations start..j: tank_from_j starts at 0, but we've already used gas[start..j-1]
# Starting at j means: tank_at_i = sum(net[j..i]) = sum(net[start..i]) - sum(net[start..j-1])
# Since sum(net[start..i]) < 0 AND sum(net[start..j-1]) >= 0 (no reset before i),
# tank_at_i when starting at j is even more negative → j cannot work either

def verify_gas_solution(gas, cost, start):
    tank = 0
    n = len(gas)
    for i in range(n):
        idx = (start + i) % n
        tank += gas[idx] - cost[idx]
        if tank < 0: return False
    return True

print(verify_gas_solution([1,2,3,4,5],[3,4,5,1,2], 3))  # True

Gas Station における総当たり法と貪欲法

def brute_force_gas(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        valid = True
        for i in range(n):
            idx = (start + i) % n
            tank += gas[idx] - cost[idx]
            if tank < 0: valid = False; break
        if valid: return start
    return -1

def greedy_gas(gas, cost):
    if sum(gas) < sum(cost): return -1
    tank = start = 0
    for i, (g, c) in enumerate(zip(gas, cost)):
        tank += g - c
        if tank < 0: tank = 0; start = i + 1
    return start

gas = [1,2,3,4,5]; cost = [3,4,5,1,2]
print('Brute:', brute_force_gas(gas,cost), '== Greedy:', greedy_gas(gas,cost))

関連: Minimum Cost to Complete Trips

def minimum_time(time, total_trips):
    def can_complete(t):
        return sum(t // bus for bus in time) >= total_trips
    
    lo, hi = 1, min(time) * total_trips  # upper bound
    while lo < hi:
        mid = (lo + hi) // 2
        if can_complete(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(minimum_time([1, 2, 3], 5))   # 3 (3/1=3 + 3/2=1 + 3/3=1 = 5)
print(minimum_time([2], 1))          # 2

境界ケースと検証

from collections import Counter

def least_interval(tasks, n):
    if n == 0: return len(tasks)  # no cooldown
    cnt = Counter(tasks)
    mf = max(cnt.values())
    mc = sum(1 for c in cnt.values() if c == mf)
    return max(len(tasks), (mf-1)*(n+1)+mc)

# Edge cases for task scheduler
print(least_interval(['A','A','A'], 2))   # 7: A _ _ A _ _ A
print(least_interval(['A','A','B','B'], 0)) # 4: no idle
print(least_interval(['A','B','C','D'], 3))  # 4: all diff, no idle needed

# Edge case for gas station
def gas_station(gas, cost):
    if sum(gas) < sum(cost): return -1
    tank = start = 0
    for i,(g,c) in enumerate(zip(gas,cost)):
        tank += g-c
        if tank < 0: tank=0; start=i+1
    return start

print(gas_station([5,1,2,3,4],[4,4,1,5,1]))  # 4

貪欲法のパターン認識

# Greedy pattern summary
# Task Scheduler:
#   Bottleneck: max frequency task
#   Formula: max(total_tasks, (max_freq-1)*(n+1)+max_count)
#   O(n) time, O(1) space

# Gas Station:
#   Bottleneck: running sum of (gas-cost) going negative
#   Reset start when tank < 0, valid if total sum >= 0
#   O(n) time, O(1) space

# Both avoid the need for DP by using a clever single-pass insight
from collections import Counter
def combined_demo(tasks, n, gas, cost):
    ti = max(len(tasks), (max(Counter(tasks).values())-1)*(n+1) +
             sum(1 for c in Counter(tasks).values() if c==max(Counter(tasks).values())))
    tank = start = 0
    gs = sum(g-c for g,c in zip(gas,cost)) >= 0
    return ti, start if gs else -1

理解度チェック

レッスンのまとめ