Myujth

Working on the following Leetcode problem: https://leetcode.com/problems/task-scheduler/

Given a char array representing tasks CPU need to do. It contains
capital letters A to Z where different letters represent different
tasks.Tasks could be done without original order. Each task could be
done in one interval. For each interval, CPU could finish one task or
just be idle.

However, there is a non-negative cooling interval n that means between
two same tasks, there must be at least n intervals that CPU are doing
different tasks or just be idle.

You need to return the least number of intervals the CPU will take to
finish all the given tasks.

Example:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

I've written code that passes the majority of the Leetcode tests cases, but is failing on a very large input. Here's my code:

import heapq
from collections import Counter

class Solution(object):
 def leastInterval(self, tasks, n):
 CLOCK = 0
 if not tasks:
 return len(tasks) 

 counts = Counter(tasks)
 unvisited_tasks = counts.most_common()[::-1]
 starting_task, _ = unvisited_tasks.pop()
 queue = [[0, starting_task]]

 while queue or unvisited_tasks:
 while queue and CLOCK >= queue[0][0]:
 _, task = heapq.heappop(queue)
 counts[task] -= 1
 if counts[task] > 0:
 heapq.heappush(queue, [CLOCK + 1 + n, task])
 CLOCK += 1

 if unvisited_tasks:
 t, _ = unvisited_tasks.pop()
 heapq.heappush(queue, [0, t])
 else:
 # must go idle
 if queue:
 CLOCK += 1

 return CLOCK 

Here's the (large) input case:

tasks = ["G","C","A","H","A","G","G","F","G","J","H","C","A","G","E","A","H","E","F","D","B","D","H","H","E","G","F","B","C","G","F","H","J","F","A","C","G","D","I","J","A","G","D","F","B","F","H","I","G","J","G","H","F","E","H","J","C","E","H","F","C","E","F","H","H","I","G","A","G","D","C","B","I","D","B","C","J","I","B","G","C","H","D","I","A","B","A","J","C","E","B","F","B","J","J","D","D","H","I","I","B","A","E","H","J","J","A","J","E","H","G","B","F","C","H","C","B","J","B","A","H","B","D","I","F","A","E","J","H","C","E","G","F","G","B","G","C","G","A","H","E","F","H","F","C","G","B","I","E","B","J","D","B","B","G","C","A","J","B","J","J","F","J","C","A","G","J","E","G","J","C","D","D","A","I","A","J","F","H","J","D","D","D","C","E","D","D","F","B","A","J","D","I","H","B","A","F","E","B","J","A","H","D","E","I","B","H","C","C","C","G","C","B","E","A","G","H","H","A","I","A","B","A","D","A","I","E","C","C","D","A","B","H","D","E","C","A","H","B","I","A","B","E","H","C","B","A","D","H","E","J","B","J","A","B","G","J","J","F","F","H","I","A","H","F","C","H","D","H","C","C","E","I","G","J","H","D","E","I","J","C","C","H","J","C","G","I","E","D","E","H","J","A","H","D","A","B","F","I","F","J","J","H","D","I","C","G","J","C","C","D","B","E","B","E","B","G","B","A","C","F","E","H","B","D","C","H","F","A","I","A","E","J","F","A","E","B","I","G","H","D","B","F","D","B","I","B","E","D","I","D","F","A","E","H","B","I","G","F","D","E","B","E","C","C","C","J","J","C","H","I","B","H","F","H","F","D","J","D","D","H","H","C","D","A","J","D","F","D","G","B","I","F","J","J","C","C","I","F","G","F","C","E","G","E","F","D","A","I","I","H","G","H","H","A","J","D","J","G","F","G","E","E","A","H","B","G","A","J","J","E","I","H","A","G","E","C","D","I","B","E","A","G","A","C","E","B","J","C","B","A","D","J","E","J","I","F","F","C","B","I","H","C","F","B","C","G","D","A","A","B","F","C","D","B","I","I","H","H","J","A","F","J","F","J","F","H","G","F","D","J","G","I","E","B","C","G","I","F","F","J","H","H","G","A","A","J","C","G","F","B","A","A","E","E","A","E","I","G","F","D","B","I","F","A","B","J","F","F","J","B","F","J","F","J","F","I","E","J","H","D","G","G","D","F","G","B","J","F","J","A","J","E","G","H","I","E","G","D","I","B","D","J","A","A","G","A","I","I","A","A","I","I","H","E","C","A","G","I","F","F","C","D","J","J","I","A","A","F","C","J","G","C","C","H","E","A","H","F","B","J","G","I","A","A","H","G","B","E","G","D","I","C","G","J","C","C","I","H","B","D","J","H","B","J","H","B","F","J","E","J","A","G","H","B","E","H","B","F","F","H","E","B","E","G","H","J","G","J","B","H","C","H","A","A","B","E","I","H","B","I","D","J","J","C","D","G","I","J","G","J","D","F","J","E","F","D","E","B","D","B","C","B","B","C","C","I","F","D","E","I","G","G","I","B","H","G","J","A","A","H","I","I","H","A","I","F","C","D","A","C","G","E","G","E","E","H","D","C","G","D","I","A","G","G","D","A","H","H","I","F","E","I","A","D","H","B","B","G","I","C","G","B","I","I","D","F","F","C","C","A","I","E","A","E","J","A","H","C","D","A","C","B","G","H","G","J","G","I","H","B","A","C","H","I","D","D","C","F","G","B","H","E","B","B","H","C","B","G","G","C","F","B","E","J","B","B","I","D","H","D","I","I","A","A","H","G","F","B","J","F","D","E","G","F","A","G","G","D","A","B","B","B","J","A","F","H","H","D","C","J","I","A","H","G","C","J","I","F","J","C","A","E","C","H","J","H","H","F","G","E","A","C","F","J","H","D","G","G","D","D","C","B","H","B","C","E","F","B","D","J","H","J","J","J","A","F","F","D","E","F","C","I","B","H","H","D","E","A","I","A","B","F","G","F","F","I","E","E","G","A","I","D","F","C","H","E","C","G","H","F","F","H","J","H","G","A","E","H","B","G","G","D","D","D","F","I","A","F","F","D","E","H","J","E","D","D","A","J","F","E","E","E","F","I","D","A","F","F","J","E","I","J","D","D","G","A","C","G","G","I","E","G","E","H","E","D","E","J","B","G","I","J","C","H","C","C","A","A","B","C","G","B","D","I","D","E","H","J","J","B","F","E","J","H","H","I","G","B","D"]
n = 1

My code is outputting an interval count of 1002, and the correct answer is 1000. Because the input size is so large, I'm having trouble debugging by hand on where this is going wrong.

My algorithm essentially does the following:

1. Build a mapping of character to number of occurrences


2. Start with the task that occurs the largest number of times.


3. When you visit a task, enqueue the next task to be CLOCK + interval iterations later, because my premise is that you want to visit a task as soon as you're able to do so.


4. If can't visit an already-visited task, enqueue a new one, and do so without incrementing the clock.


5. If you have elements in the queue, but not enough time has passed, increment the clock.

At the end, the CLOCK variable describes how long (in other words, how many "intervals") passed before you're able to run all tasks.

Can someone spot the bug in my logic?

Consider a case where the delay n=1, and you have a task distribution like so, for which the least number of cycles is just the length of the list (the tasks could be run like "ABCABC...D"):

"A": 100, "B": 100, "C": 99, "D": 1 # { "task": <# of occurrences>, ...

Using your algorithm, you would process all the cases of "A" and "B" first, since you want to move onto the next task in the same type as soon as possible, without considering other task types. After processing those two, you're left with:

"C": 99, "D": 1

which results in at least 96 idle cycles.

To fix this, the ideal task configuration would be something like a round robin of sorts.