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

Solution 1

One possible solution is to build sequence symbol by symbol, each moment of time taking the most frequent from the rest symbols, but also such that it is not used in last $n$ iterations. One way is to keep just frequencies of all letters and when we use letter, make frequency negative. On each iteration we choose element with highest frequency, in this way we ignore elements with negative frequencies. Time complexity is $O(26m)$, where $m$ is length of tasks, space complexity is $O(n)$ to keep our queue .

class Solution:
    def leastInterval(self, tasks, n):
        freq, units, queue = [0]*26, 0, deque()

        for elem in tasks:
            freq[ord(elem) - ord("A")] += 1
        
        Rest = len(Counter(tasks))

        while Rest != 0:
            if len(queue) == n + 1:
                old = queue.popleft()
                if old < 26: freq[old] *= (-1)
            
            Max_freq = max(freq)
            Max_freq_ind = freq.index(max(freq))
            if Max_freq == 0: 
                queue.append(26)
            else:
                freq[Max_freq_ind] = 1 - freq[Max_freq_ind]
                if freq[Max_freq_ind] == 0: Rest -= 1
                queue.append(Max_freq_ind)
            units += 1
        
        return units

Solution 2

Alternatively, we can use heap to find maximum with lazy deletion with time complexity $O(m\log 26)$ and space complexity $O(n)$.

class Solution(object):
    def leastInterval(self, tasks, n):
        c = Counter(tasks)
        heap = [(-c[key], key) for key in c]
        heapq.heapify(heap)
        buff, res, Rest = deque(), 0, len(heap)

        while Rest != 0:
            if heap:
                curCharKey, curCharVal = heapq.heappop(heap)
                res += 1
                curCharKey += 1
                if curCharKey == 0: Rest -= 1
                buff.append((curCharKey, curCharVal))

            if len(buffer) == n + 1:
                curCharKey, curCharVal = buff.popleft()
                if curCharKey < 0:
                    heapq.heappush(heap, (curCharKey, curCharVal))

            if not heap or (len(buff) == n+1 and curCharKey == 0):
                heapq.heappush(heap, (0, "#"))
        
        return res

Solution 3

This is quite difficult problem if you want to have optimal solution. First, I tried several ideas, using queue and greedy algorithm, where I tried to build sequence symbol by symbol, but it was working very slow and I get TLE. So, I decided to stop coding and to think.

So, what is the main trick? First of all notice, that what is matter, is frequence of each letter, not order. For each letter we need to evaluate minimum window size we need to fully use this letter. For example, if we have 4 letters A in our tasks and n = 3, then minimum window looks like A...A...A...A. So, the minimum length in this case we need is 13 = (n+1) * 3 + 1. Let us call this number 13 characteristic of letter A. More examples:

  1. If n = 4 and we have BBBBB, than characteristic of letter B is equal to (n+1) * 4 + 1 = 21.
  2. If n = 1 and we have CC, than characteristic of letter C is equal to (n+1) * 1 + 1 = 3.

So, we need to evaluate characteristics of all letters and just choose the maximum one? Similar, but not exaclty. What if we have two letters with the same characteristic (it means they have the same frequencies), like we have AAAABBBB. Then we need to have window A...A...A...A and also window B...B...B...B, and you can not put one inside another. So, in this case we need at least one symbol more, and example will be AB..AB..AB..AB.

In this problem we are asked, what is the minimum number of units we need to use, so, mathematicaly speaking, we need to do two steps:

  1. Estimation: prove, that we need at least say k units.
  2. Give an example for this k units, how to construct desired sequence. (note, that in this problem you do not really ask to create example, but we still need to prove, that it exists).

We already considered Estimation: we need to find elements with the highest characteristic and check how many such elements we have. So, if freq = Counter(tasks) and Most_freq = freq.most_common()[0][1] is the element with highest frequency, than Found_most = sum([freq[key] == Most_freq for key in freq]) is number of such elements and we return max(len(tasks), (Most_freq - 1) * (n + 1) + Found_most), because we can not be shorter than len(tasks).

The most difficult part is to prove that example exists. Let us consider case, where we have AAAA, BBBB, n = 5 and also we have some letters. Then first step is to build:

AB....AB....AB....AB

What we know about other elements? Their frequencies are less than Most_freq = 4. So, let us start to fill dots in special order:

A B 1 4 7 10 A B 2 5 8 11 A B 3 6 9 12 A B

Why we choose this order? Because for any Most_freq - 2 elements with adjacent numbers, places will be at least n elements apart! So all we need to do is to fill elements with frequencies Most_freq - 1 first, and then fill all the other empty places.

There is another case, where (Most_freq - 1) * (n + 1) + Found_most < len(tasks), for example when we have something like AABBCCD, n = 2 In this case we can show that answer should be equal to len(tasks). We again start with most with most common letters and try to form answer. However we can see, that we can not combine properly A.A, B.B and C.C like we did previously, so we combine them as ABCABC. The last step is to insert remaining letters between constructed string. It is not very strict explanation, but I hope it helps.

Complexity: time complexity is O(n), to evaluate freq and one more pass to find all elements with highest frequency. Then we just evaluate answer in constant time. Space complexity is O(26), because there are 26 different letters.

class Solution:
    def leastInterval(self, tasks, n):
        freq = Counter(tasks)
        Most_freq = freq.most_common()[0][1]
        Found_most = sum([freq[key] == Most_freq for key in freq])
        return max(len(tasks), (Most_freq - 1) * (n + 1) + Found_most)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0621