621. Task Scheduler

Medium

Problem:

There are tasks represented from A to Z. At each interval, the CPU can execute only one task, and the same task cannot be executed within 'n' intervals. If no further tasks can be executed, the CPU enters an idle state. Output the minimum number of intervals required to execute all tasks.

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

https://leetcode.com/problems/task-scheduler/

What to learn:

collections.Counter()

A notable feature of the Counter is that it also handles zeros and negative numbers. Thus, adding an empty collection.Counter() will completely remove items with counts of zero or less from the list.

most_common()

The most_common() function outputs the items with the highest count first, essentially serving the same role as a maximum heap. However, the items are not extracted using pop().

Solution:

A priority queue should be used to extract the items with the highest count one by one, but the challenge is not to extract everything at once. Instead, we need a structure that allows us to update the count after only one extraction.

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

        while True:
            sub_count = 0
            for task, _ in counter.most_common(n + 1):
                sub_count += 1
                result += 1

                counter.subtract(task)
                # Remove zero and negative counts
                counter += collections.Counter()
            if not counter:
                break
            # Cooldown period
            result += n - sub_count + 1

        return result

Consider the tasks:

codetasks = ["A", "A", "A", "A", "B", "B", "C", "D", "E"]
n = 2

Here, task "A" appears most frequently. Our goal is to minimize idle times, which means we need to schedule "A" in a manner that we don't end up in a position where we're forced to be idle waiting to schedule it again.

1. Initial State:

• counter = {A:4, B:2, C:1, D:1, E:1}

• result = 0

2. First Iteration:

We fetch the top n + 1 = 3 most frequent tasks. Why 3? Because within a span of 3 time units, we can perform the same task just once (i.e., the task "A" in this case) due to the cooldown period.

• counter.most_common(3) returns [("A", 4), ("B", 2), ("C", 1)].

• We schedule these tasks in the order they're returned:

  1. "A" - counter becomes {A:3, B:2, C:1, D:1, E:1}.

  2. "B" - counter becomes {A:3, B:1, C:1, D:1, E:1}.

  3. "C" - counter becomes {A:3, B:1, D:1, E:1}.

Our schedule now is: A -> B -> C.

• No two adjacent tasks are the same, which ensures the cooldown period is maintained.

• result is incremented by 3.

3. Second Iteration:

We again fetch the top n + 1 = 3 tasks.

• counter.most_common(3) returns [("A", 3), ("B", 1), ("D", 1)].

• Schedule:

  1. "A" - counter becomes {A:2, B:1, D:1, E:1}.

  2. "B" - counter becomes {A:2, D:1, E:1}.

  3. "D" - counter becomes {A:2, E:1}.

Schedule now: A -> B -> C -> A -> B -> D.

• Again, no two adjacent tasks are the same.

• result increments by 3 and becomes 6.

4. Third Iteration:

We fetch top 3 tasks.

• counter.most_common(3) returns [("A", 2), ("E", 1)]. Notice we have only 2 tasks this time.

• Schedule:

  1. "A" - counter becomes {A:1, E:1}.

  2. "E" - counter becomes {A:1}.

Schedule: A -> B -> C -> A -> B -> D -> A -> E.

Now, this is important:

• We scheduled 2 tasks, but our slot size based on cooldown is 3 (remember, n + 1). Hence, to ensure the next "A" isn't scheduled within the cooldown period, we need an idle time.

Schedule becomes: A -> B -> C -> A -> B -> D -> A -> E -> idle.

• result increments by 3 (2 tasks + 1 idle).

5. Fourth Iteration:

Only "A" remains.

• Schedule "A".

Final schedule: A -> B -> C -> A -> B -> D -> A -> E -> idle -> A.

• result becomes 10.

In essence, by always trying to schedule the top n + 1 tasks, we're ensuring two things:

1. We're optimizing our task execution order to minimize idle times.

2. We're inherently ensuring that no two same tasks are adjacent because, in a span of n + 1 time units, we're executing the same task only once.