← 전체 회차
a-068-task-scheduler2026-07-20mediumleetcode #621neetcode150

CPU 작업 스케줄링

#array#hash-table#greedy#sorting#heap-priority-queue#counting
↗ leetcode #621 · a-068-task-scheduler
01

문제

· problem
P.a-068-task-scheduler

CPU 작업 스케줄링

↗ leetcode #621

A부터 Z까지의 레이블이 있는 CPU 작업 배열이 주어집니다. 또한 정수 n이 주어집니다. 각 CPU 구간은 유휴 상태이거나 하나의 작업을 완료할 수 있습니다. 작업은 어떤 순서로든 완료될 수 있지만, 같은 레이블의 두 작업 사이에는 최소 n개의 구간만큼의 간격이 있어야 합니다. 모든 작업을 완료하는 데 필요한 최소 CPU 구간 수를 반환하세요.

제약
  • · 1 ≤ tasks.length ≤ 10⁴
  • · tasks[i] is an uppercase English letter
  • · 0 ≤ n ≤ 100
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["A","A","A","B","B","B"]
2
8
example 2input → output
["A","C","A","B","D","B"]
1
6
example 3input → output
["A","A","A", "B","B","B"]
3
10
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    같은 레이블의 작업 사이에 'n개의 구간 간격'은 정확히 무엇을 의미하나요?
  • ☐
    가장 빈번한 작업을 우선으로 처리하면 왜 최적해를 보장하나요?
  • ☐
    모든 작업이 서로 다르면 답은 어떻게 되나요?
  • ☐
    n=0이면 답은 무엇인가요?
  • ☐
    큐에 저장되는 [cnt, time + n] 값은 무엇을 의미하나요?
  • ☐
    Python의 heapq가 최소 힙인데 왜 음수를 사용하여 최대 힙을 만드나요?
  • ☐
    시간을 q[0][1]로 점프하는 것은 언제 발생하고 왜 필요한가요?
  • ☐
    1 + heappop() 후 cnt가 0이 되면 그 작업은 완전히 완료된 건가요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 각 작업의 빈도 계산
○
count = Counter(tasks)
○
count = set(tasks)
○
count = {task: len([t for t in tasks if t == task]) for task in set(tasks)}
step 2· 최대 힙 구성 (음수 변환)
○
maxHeap = [-cnt for cnt in count.values()]
○
maxHeap = list(count.values())
○
maxHeap = sorted([-cnt for cnt in count.values()], reverse=True)
step 3· 주 시뮬레이션 루프
○
while maxHeap or q:
○
while maxHeap:
○
while q:
step 4· 시간 관리 및 유휴 처리│ 중첩
○
time = q[0][1]
○
time += n
○
if not maxHeap: time += 1
step 5· 가장 빈번한 작업 실행│ 중첩
○
cnt = 1 + heapq.heappop(maxHeap)
○
cnt = heapq.heappop(maxHeap)
○
cnt = 1 + heapq.heappop(maxHeap) - 1
step 6· 냉각 제약 관리 및 작업 복원│ 중첩
○
if q and q[0][1] == time:
○
if q and q[0][1] < time:
○
while q and q[0][1] == time:
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def leastInterval(self, tasks: List[str], n: int) -> int:
3
        count = Counter(tasks)
4
        maxHeap = [-cnt for cnt in count.values()]
5
        heapq.heapify(maxHeap)
6
7
        time = 0
8
        q = deque()  # pairs of [-cnt, idleTime]
9
        while maxHeap or q:
10
            time += 1
11
12
            if not maxHeap:
13
                time = q[0][1]
14
            else:
15
                cnt = 1 + heapq.heappop(maxHeap)
16
                if cnt:
17
                    q.append([cnt, time + n])
18
            if q and q[0][1] == time:
19
                heapq.heappush(maxHeap, q.popleft()[0])
20
        return time
21
22
23
# Greedy algorithm
24
class Solution(object):
25
    def leastInterval(self, tasks: List[str], n: int) -> int:
26
        counter = collections.Counter(tasks)
27
        max_count = max(counter.values())
28
        min_time = (max_count - 1) * (n + 1) + \
29
                    sum(map(lambda count: count == max_count, counter.values()))
30
    
31
        return max(min_time, len(tasks))
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["A","A","A","B","B","B"]
2
→
8
case 2
["A","C","A","B","D","B"]
1
→
6
case 3
["A","A","A", "B","B","B"]
3
→
10
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.