Given a character array tasks of size N, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
CPU has a cooldown period for each task. CPU can repeat a task only after atleast K units of time has passed after it did same task last time. It can perform other tasks in that time, can stay idle to wait for repeating that task.
Return the least number of units of times that the CPU will take to finish all the given tasks.
Example 1:
Input:
N = 6
K = 2
task[ ] = {'A', 'A', 'A', 'B', 'B', 'B'}
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is atleast 2 units of time between any two same tasks.
 
Example 2:
Input:
N = 12
K = 2
task[ ] = {'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'}
Output: 16
Explanation:  
One possible solution is 
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function leastInterval() which takes the interger N, integer K and an character array tasks as parameters and returns the minimum unit of time required to complete all tasks.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ K ≤ 100
task_{i }is upper-case English letter.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def leastInterval(self, N, K, tasks):

        # Code here

Solutions:
import heapq

class Solution:

	def leastInterval(self, N, K, tasks):
		dic = {}
		for i in tasks:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		ans = 0
		heap = []
		for i in dic:
			heapq.heappush(heap, [-dic[i], i])
		while heap:
			temp = []
			p = heapq.heappop(heap)
			ans += 1
			p[0] = -p[0]
			p[0] -= 1
			if p[0] > 0:
				p[0] = -p[0]
				temp.append(p)
			if len(heap) >= K:
				for i in range(K):
					p = heapq.heappop(heap)
					ans += 1
					p[0] = -p[0]
					p[0] -= 1
					if p[0] > 0:
						p[0] = -p[0]
						temp.append(p)
			else:
				if len(temp) > 0:
					ans += K - len(heap)
				for i in range(len(heap)):
					p = heapq.heappop(heap)
					ans += 1
					p[0] = -p[0]
					p[0] -= 1
					if p[0] > 0:
						p[0] = -p[0]
						temp.append(p)
			for i in range(len(temp)):
				heapq.heappush(heap, temp[i])
		return ans


class Solution:

	def leastInterval(self, N, K, tasks):
		curtime = 0
		dict_next = dict()
		dict_rem = dict()
		for i in tasks:
			if i not in dict_next:
				dict_next[i] = 0
			if i not in dict_rem:
				dict_rem[i] = 1
			elif i in dict_rem:
				dict_rem[i] += 1
		while len(dict_rem) > 0:
			for i in dict_rem:
				if dict_next[i] <= curtime:
					dict_next[i] += K + 1
					dict_rem[i] -= 1
					if dict_rem[i] == 0:
						del dict_rem[i]
					break
			curtime += 1
		return curtime


import heapq
from collections import deque

class Solution:

	def leastInterval(self, n, k, tasks):
		count = {}
		for i in range(n):
			count[tasks[i]] = 1 + count.get(tasks[i], 0)
		maxHeap = [-1 * cnt for cnt in count.values()]
		heapq.heapify(maxHeap)
		q = deque()
		time = 0
		while maxHeap or q:
			time += 1
			if maxHeap:
				cnt = 1 + heapq.heappop(maxHeap)
				if cnt:
					q.append([cnt, time + k])
			if q and q[0][1] == time:
				heapq.heappush(maxHeap, q.popleft()[0])
		return time


import heapq

class Solution:

	def leastInterval(self, N, k, tasks):
		dic = {}
		for el in tasks:
			if el in dic:
				dic[el] += 1
			else:
				dic[el] = 1
		ans = 0
		hp = []
		for el in dic:
			heapq.heappush(hp, [-dic[el], el])
		while hp:
			par = []
			p = heapq.heappop(hp)
			ans += 1
			p[0] = -p[0]
			p[0] -= 1
			if p[0] > 0:
				p[0] = -p[0]
				par.append(p)
			if len(hp) >= k:
				for i in range(k):
					p = heapq.heappop(hp)
					ans += 1
					p[0] = -p[0]
					p[0] -= 1
					if p[0] > 0:
						p[0] = -p[0]
						par.append(p)
			else:
				if len(par) > 0:
					ans += k - len(hp)
				for i in range(len(hp)):
					p = heapq.heappop(hp)
					ans += 1
					p[0] = -p[0]
					p[0] -= 1
					if p[0] > 0:
						p[0] = -p[0]
						par.append(p)
			for m in range(len(par)):
				heapq.heappush(hp, par[m])
		return ans


import heapq
from collections import defaultdict

class Solution:

	def leastInterval(self, N, k, tasks) -> int:
		freq_map = defaultdict(int)
		for task in tasks:
			freq_map[task] += 1
		pq = []
		for (task, freq) in freq_map.items():
			heapq.heappush(pq, (-freq, task))
		t = 0
		while pq:
			size = k + 1
			idle = 0
			if len(pq) < k + 1:
				size = len(pq)
				idle = k + 1 - len(pq)
			t += size
			temp = []
			for i in range(size):
				if pq:
					(freq, task) = heapq.heappop(pq)
					freq += 1
					if freq < 0:
						temp.append((freq, task))
			for task in temp:
				heapq.heappush(pq, task)
			if pq:
				t += idle
		return t


from collections import Counter, deque
from heapq import heapify, heappush, heappop

class Solution:

	def leastInterval(self, N, K, tasks):
		count = Counter(tasks)
		maxHeap = [-cnt for cnt in count.values()]
		heapify(maxHeap)
		time = 0
		q = deque()
		while maxHeap or q:
			time += 1
			if maxHeap:
				cnt = 1 + heappop(maxHeap)
				if cnt:
					q.append([cnt, K + time])
			if q and q[0][1] == time:
				heappush(maxHeap, q.popleft()[0])
		return time


class Solution:

	def leastInterval(self, N, K, tasks):
		let = [0 for i in range(26)]
		p = 0
		for i in tasks:
			p = ord(i) - ord('A')
			let[p] += 1
		q = c = 0
		for i in range(26):
			if let[i] > q:
				q = let[i]
				c = 1
			elif let[i] == q:
				c += 1
		return max((q - 1) * (K + 1) + c, N)


from collections import deque
from collections import Counter
import heapq

class Solution:

	def leastInterval(self, N, K, tasks):
		c = Counter(tasks)
		heap = [x for x in c.values()]
		heapq._heapify_max(heap)
		time = 0
		q = deque()
		while heap or q:
			time += 1
			if heap:
				count = heapq._heappop_max(heap)
				count -= 1
				if count:
					q.append([count, time + K])
			if q and q[0][1] == time:
				heap.append(q[0][0])
				heapq._siftdown_max(heap, 0, len(heap) - 1)
				q.popleft()
		return time


from collections import deque
import heapq
from collections import Counter

class Solution:

	def leastInterval(self, N, K, tasks):
		hp = []
		q = deque()
		c = Counter(tasks)
		for key in c:
			heapq.heappush(hp, -c[key])
		time = 0
		while hp or q:
			time += 1
			if hp:
				count = heapq.heappop(hp)
				count += 1
				if count < 0:
					q.appendleft((time + K, count))
			if q and q[-1][0] == time:
				count = q.pop()[1]
				heapq.heappush(hp, count)
		return time


import heapq
from collections import deque

class Solution:

	def leastInterval(self, N, K, tasks):
		q = deque()
		freq = {}
		for ele in tasks:
			freq[ele] = 1 + freq.get(ele, 0)
		maxheap = [-cnt for cnt in freq.values()]
		heapq.heapify(maxheap)
		time = 0
		while maxheap or q:
			time += 1
			if maxheap:
				cnt = 1 + heapq.heappop(maxheap)
				if cnt:
					q.append((cnt, time + K))
			if q and q[0][1] == time:
				avail = q.popleft()
				heapq.heappush(maxheap, avail[0])
		return time


class Solution:

	def leastInterval(self, N, k, tasks):
		from collections import Counter
		import heapq
		a = Counter(tasks)
		q = [(-c, ele) for (ele, c) in a.items()]
		heapq.heapify(q)
		time = 0
		rem = []
		while q:
			for i in range(k + 1):
				if q or rem:
					time += 1
				if q:
					(count, ele) = heapq.heappop(q)
					if count < -1:
						rem.append((count + 1, ele))
			while rem:
				heapq.heappush(q, rem.pop())
		return time


from collections import Counter

class Solution:

	def leastInterval(self, N, K, tasks):
		count = Counter(tasks)
		maxFreq = max(count.values())
		maxFreqTasksCount = list(count.values()).count(maxFreq)
		parts = maxFreq - 1
		partLength = K - (maxFreqTasksCount - 1)
		emptySlots = parts * partLength
		availableTasks = N - maxFreq * maxFreqTasksCount
		Idles = max(0, emptySlots - availableTasks)
		return Idles + len(tasks)


from collections import Counter, deque
from heapq import heappop, heappush, heapify

class Solution:

	def leastInterval(self, N, K, tasks):
		count = Counter(tasks)
		maxOccur = max(count.values())
		time = (maxOccur - 1) * (K + 1)
		for i in count.keys():
			if count[i] == maxOccur:
				time += 1
		return max(N, time)


from queue import PriorityQueue

class Solution:

	def leastInterval(self, N, K, arr):
		mp = {i: 0 for i in arr}
		for i in arr:
			mp[i] += 1
		ma = max(list(mp.values()))
		answer = (ma - 1) * (K + 1)
		for i in mp.keys():
			if mp[i] == ma:
				answer += 1
		return max(len(arr), answer)


from collections import Counter

class Solution:

	def leastInterval(self, N, K, tasks):
		mp = Counter(tasks)
		count = max(mp.values())
		ans = (count - 1) * (K + 1)
		for (key, val) in mp.items():
			if val == count:
				ans += 1
		return max(len(tasks), ans)


class Solution:

	def leastInterval(self, N, n, tasks):
		freq = {}
		for task in tasks:
			if task not in freq:
				freq[task] = 1
			else:
				freq[task] += 1
		freq = [value for (key, value) in freq.items()]
		max_freq = max(freq)
		max_freq_tasks = freq.count(max_freq)
		return max(len(tasks), (max_freq - 1) * (n + 1) + max_freq_tasks)