Leetcode 621. 任务调度器
注意的点:
1、这道题是一个贪心算法,解法主要是按照排列组合里的插入方法去思考。
2、思路:先统计最大频率出现的元素用来做分隔板,然后再去考虑插入的问题,与排列组合的思想一致。
- (n+1)表示空余位置和隔板位置差一位 (most_frequence - 1)表示间隔数比总元素数差一位
- 加most_frequence_repeat表示计算最大元素隔板后面还跟着多少的尾巴。
- 与数组长度求最大值含义是在满足最大元素的需求的基础上,其他元素随意往里插入就行,不会引起空白位置的增加。
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
from collections import Counter
c = Counter(tasks).most_common() # ('A', 3)
most_frequence = c[0][1]
most_frequence_repeat = 0
for each_tuple in c:
if each_tuple[1] == most_frequence: most_frequence_repeat += 1
return max(len(tasks), (n + 1) * (most_frequence - 1) + most_frequence_repeat)