Task Scheduler

The problem description can be found in LeetCode.

Approach

A greedy approach can be used to solve this problem.

By deriving some examples, we can prove that the best way to start would be to select the most frequent tasks and then continue with the other ones.

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

If we select B first we would have the sequence:

B -> A -> idle -> idle -> A -> idle -> idle -> A -> idle -> idle

However, if we select A first:

A -> B -> A -> idle -> idle -> A

Once the most frequent task is completed, we can decrease its number of occurrences by one and still use it for the next iteration if the number is not 0.

An efficient data structure that allows this is the Heap.

Solution

import heapq
from typing import List


class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = self.get_chars_counter(tasks)

        heap = [-occ for occ in counter if occ > 0]
        heapq.heapify(heap)

        ans = 0
        while heap:
            remained_tasks = []
            completed_tasks = 0

            for _ in range(n + 1):
                if not heap:
                    break

                completed_tasks += 1

                occ = -heapq.heappop(heap) - 1
                if occ > 0:
                    remained_tasks.append(-occ)

            for task in remained_tasks:
                heapq.heappush(heap, task)

            ans += completed_tasks if not heap else n + 1

        return ans

    def get_chars_counter(self, tasks: List[str]) -> List[int]:
        m = [0] * 26

        for task in tasks:
            assert isinstance(task, str)
            assert len(task) == 1

            idx = ord(task) - ord("A")
            m[idx] += 1

        return m

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the tasks list.