"""Leetcode 621. Task Scheduler
Medium

URL: 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 differenttasks. 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.

Note:
- The number of tasks is in the range [1, 10000].
- The integer n is in the range [0, 100].
"""

class SolutionTaskCountDictMaxHeap(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int

        Time complexity: O(m), where m is the length of tasks.
        Space complexity: O(m).
        """
        from collections import defaultdict
        import heapq

        # Create dict: task->count.
        task_count_d = defaultdict(int)
        for t in tasks:
            task_count_d[t] += 1

        # Push tasks/counts into max heap (min heap with negative keys).
        neg_count_minheap = [-c for c in task_count_d.values()]
        heapq.heapify(neg_count_minheap)

        cycles = 0

        while neg_count_minheap:
            # Collect cycle tasks, denoted by their negative counts.
            cycle_tasks = []

            # Run n + 1 tasks, 1 for 1sttask and n for cooling.
            for i in range(n + 1):
                if neg_count_minheap:
                    cycle_tasks.append(-heapq.heappop(neg_count_minheap))

            # If specific task exists after processed one, add back to maxheap.
            for j in cycle_tasks:
                if j > 1:
                    heapq.heappush(neg_count_minheap, -(j - 1))

            # Add cycles for the last batch of tasks, or continue.  
            if not neg_count_minheap:
                cycles += len(cycle_tasks)
            else:
                cycles += n + 1

        return cycles


def main():
    # Output: 8.
    tasks = ["A","A","A","B","B","B"]
    n = 2
    print SolutionTaskCountDictMaxHeap().leastInterval(tasks, n)

    # Output: 16.
    tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"]
    n = 2
    print SolutionTaskCountDictMaxHeap().leastInterval(tasks, n)


if __name__ == '__main__':
    main()

@@ -217,16 +217,17 @@
 ifferent
+ 
 tasks. T
@@ -1430,25 +1430,24 @@
 %0A        neg
-_
 count_minhea
@@ -1507,25 +1507,24 @@
 .heapify(neg
-_
 count_minhea
@@ -1531,24 +1531,26 @@
 p)%0A%0A        
+n_
 cycles = 0%0A%0A
@@ -1562,25 +1562,24 @@
    while neg
-_
 count_minhea
@@ -1720,16 +1720,17 @@
  for 1st
+ 
 task and
@@ -1798,25 +1798,24 @@
       if neg
-_
 count_minhea
@@ -1870,25 +1870,24 @@
 .heappop(neg
-_
 count_minhea
@@ -2069,17 +2069,16 @@
 push(neg
-_
 count_mi
@@ -2113,16 +2113,35 @@
   # Add 
+full cycles or add 
 cycles f
@@ -2170,21 +2170,8 @@
 asks
-, or continue
 .  %0A
@@ -2189,16 +2189,11 @@
  if 
-not 
 neg
-_
 coun
@@ -2211,32 +2211,34 @@
                 
+n_
 cycles += len(cy
@@ -2235,24 +2235,13 @@
  += 
-len(cycle_tasks)
+n + 1
 %0A   
@@ -2267,24 +2267,26 @@
             
+n_
 cycles += n 
@@ -2283,21 +2283,32 @@
 cles += 
-n + 1
+len(cycle_tasks)
 %0A%0A      
@@ -2316,16 +2316,18 @@
  return 
+n_
 cycles%0A%0A

Revise adding n_cycles