Task Scheduler

---

Intuition

• For a task to be schedulable, it must be available. For it to be available, there must be n seconds elapsed after that task has been scheduled.
• Utilize a heap with counts of each task. The first task to be scheduled should always be the one that occurs the most, since by selecting the one which occurs most, idling is avoided in the case where the only task remaining is the one that occurred most, forcing an idle since you used up the tasks that remained less times.
• Utilize a queue to keep track of the time in which that amount of tasks left can be scheduled again.
• Place back in the heap the task to be scheduled again from the queue, since it should contend with the other tasks as to which one occurs first.

Complexity

Runtime

$O(N)$ to build the heap of N tasks.

• Only $\log (26)$ for the while loop since we push or insert from only 26 possible letter tasks.

Space

$O(N)$

Code

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        c = Counter(tasks)
        heap = [-count for count in c.values()]
        heapify(heap)
        q = deque()
        ct = 0
 
        while heap or q:
            if q and q[0][1] == ct:
                amt, _ = q.popleft()
                heappush(heap, -amt)
            if heap:
                amt = -heappop(heap)
                if amt - 1 > 0:
                    q.append((amt - 1, ct + n + 1))
            ct += 1
 
        return ct

Notes

Cards

START Basic Front: Task Scheduler Back: Use a heap in a greedy fashion with most occurring first, followed by a queue of which task to schedule next. END

---

References

• Task Scheduler
• ChatGPT Code Tutor