Heap-PrioiryQueue: 621. Task Scheduler ★★★

621. Task Scheduler

 

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # each task takes 1 unit of time
        # minimize idle time
        # 각 작업은 1 단위 시간만 소요되며, 유휴 시간을 최소화하는 것이 목표

        # Count the frequency of each task
        # 각 작업의 빈도를 세어서 저장
        count = Counter(tasks)  # 예: {"A": 3, "B": 3, "C": 1}

        # Convert the task counts to a max heap (negative values for max heap)
        # 최대 힙을 사용하기 위해 빈도를 음수로 변환하여 저장
        maxHeap = [-cnt for cnt in count.values()]  # 예: [-3, -3, -1]

        # Transform the list into a valid heap
        # 리스트를 힙 자료구조로 변환
        heapq.heapify(maxHeap)  # 최소 힙으로 동작하며 음수 값을 통해 최대 힙처럼 사용

        # Initialize the time counter
        # 총 실행 시간을 기록하는 변수
        time = 0

        # Queue to track tasks waiting for cooldown
        # 대기 상태에 있는 작업과 해당 작업이 다시 실행 가능한 시간을 저장하는 큐
        q = deque()  # 큐는 (작업 남은 빈도, 재실행 가능한 시간)의 쌍을 저장

        # Process tasks until both the heap and the queue are empty
        # 힙과 큐가 모두 빌 때까지 작업 처리
        while maxHeap or q:
            # Increment the time for each interval
            # 각 단위 시간마다 증가
            time += 1

            # If there are tasks in the max heap, process one
            # 힙에 작업이 남아 있으면 하나를 처리
            if maxHeap:
                cnt = 1 + heapq.heappop(maxHeap)  # 작업 하나를 처리하고 남은 횟수를 계산
                if cnt:  # 작업이 아직 남아 있는 경우
                    # Add the task to the cooldown queue with its next executable time
                    # 작업을 대기 큐에 추가하고, 재실행 가능한 시간을 설정
                    q.append([cnt, time + n])  # 재실행 가능한 시간 = 현재 시간 + 냉각 시간

            # If the front of the queue is ready to be executed, push it back to the heap
            # 대기 큐의 작업이 재실행 가능해졌다면 힙에 다시 추가
            if q and q[0][1] == time:
                heapq.heappush(maxHeap, q.popleft()[0])  # 작업을 힙에 다시 추가

        # Return the total time taken to complete all tasks
        # 모든 작업을 완료하는 데 소요된 총 시간 반환
        return time

 

코드 동작 상세

1. Counter로 작업 빈도 계산

• 각 작업이 몇 번 등장했는지 계산하여 Counter 객체에 저장합니다.
• 이를 통해 작업의 빈도를 추적할 수 있습니다.

2. 최대 힙 생성

• 최대 힙은 가장 빈도가 높은 작업을 먼저 처리하도록 도와줍니다.
• Python의 heapq는 기본적으로 최소 힙이므로, 작업 빈도에 음수를 곱해 최대 힙처럼 동작하도록 변환합니다.

3. 대기 큐 사용

• 동일 작업 간의 냉각 시간(n)을 유지하기 위해 deque를 사용합니다.
• 대기 큐에는 (작업의 남은 빈도, 작업이 다시 실행 가능한 시간) 형태로 저장됩니다.

4. 시간 흐름 관리

• 시간(time)은 작업을 처리하거나 대기 상태를 유지할 때마다 증가합니다.

5. 작업 처리

• 매 시간마다 힙에서 작업을 꺼내 처리합니다.
• 처리된 작업은 대기 큐에 추가되며, 냉각 시간이 지난 후 다시 힙에 추가됩니다.

6. 종료 조건

• 힙과 대기 큐가 모두 비어야 모든 작업이 완료되므로, 이 조건을 만족할 때까지 루프가 실행됩니다.

예제2)

Input: tasks = ["A","C","A","B","D","B"], n = 1

 

1. 작업 빈도 계산

Counter로 작업의 빈도를 계산합니다.

count = Counter(tasks)

 

=> count = {"A": 2, "B": 2, "C": 1, "D": 1}

 

 

2. 최대 힙 생성

작업의 빈도를 음수로 변환하여 최대 힙을 만듭니다.

maxHeap = [-cnt for cnt in count.values()]

heapq.heapify(maxHeap)

 

=> maxHeap = [-2, -2, -1, -1]

3. 초기화

• time = 0: 총 실행 시간을 기록하는 변수.
• q = deque(): 대기 큐를 생성하여 (남은 작업 횟수, 다시 실행 가능한 시간) 저장.

4. 작업 처리

while 루프를 통해 힙과 대기 큐가 비워질 때까지 작업을 처리합니다.

시간 1:

• time = 1: 증가.
• 힙에서 작업 A(빈도 -2)를 꺼냄.
  cnt = 1 + heapq.heappop(maxHeap)
  => cnt = -1
• A의 남은 작업 횟수는 1회. 대기 큐에 추가:
   

  q.append([cnt, time + n])
  => q = [[-1, 2]]

시간 2:

• time = 2: 증가.
• 힙에서 작업 B(빈도 -2)를 꺼냄.
  cnt = 1 + heapq.heappop(maxHeap)
  => cnt = -1
• B의 남은 작업 횟수는 1회. 대기 큐에 추가:
   

  q.append([cnt, time + n])
  => q = [[-1, 2], [-1, 3]]
• 대기 큐의 첫 번째 작업(A)이 다시 실행 가능:
  heapq.heappush(maxHeap, q.popleft()[0])
  => maxHeap = [-1, -1]

시간 3:

• time = 3: 증가.
• 힙에서 작업 A(빈도 -1)를 꺼냄.
   

  cnt = 1 + heapq.heappop(maxHeap) # cnt = 0
• A는 더 이상 남은 작업이 없으므로 대기 큐에 추가되지 않음.
• 대기 큐의 첫 번째 작업(B)이 다시 실행 가능:
  heapq.heappush(maxHeap, q.popleft()[0]) # maxHeap = [-1]

시간 4:

• time = 4: 증가.
• 힙에서 작업 B(빈도 -1)를 꺼냄.
  cnt = 1 + heapq.heappop(maxHeap) # cnt = 0
• B는 더 이상 남은 작업이 없으므로 대기 큐에 추가되지 않음.

시간 5:

• time = 5: 증가.
• 힙에서 작업 C(빈도 -1)를 꺼냄.
  cnt = 1 + heapq.heappop(maxHeap) # cnt = 0
• C는 더 이상 남은 작업이 없으므로 대기 큐에 추가되지 않음.

시간 6:

• time = 6: 증가.
• 힙에서 작업 D(빈도 -1)를 꺼냄.
  cnt = 1 + heapq.heappop(maxHeap) # cnt = 0
• D는 더 이상 남은 작업이 없으므로 대기 큐에 추가되지 않음.

---

최종 결과

모든 작업이 완료되었으므로 총 시간은 6입니다.

결과 작업 순서

• A -> B -> A -> B -> C -> D

작업 간 n = 1의 간격을 유지하면서 모든 작업을 처리