LeetCode Medium621タスクスケジューリング-最小間隔Python

Leetcode Medium 621 Task Scheduling Minimum Interval Python

def leastInterval(self, tasks, n): ''' Solution Method From the example we can get the rules of task scheduling. As given: AAABBCD, n=2. Then we can meet the task interval requirements by satisfying the number of tasks required by the most number of tasks, namely: AXXAXXA (where X indicates the interval at which the task or idle needs to be filled) If there are two or more tasks with the same maximum number of tasks, such as: AAAABBBBCCDE, n=3. Then we will have the same number of tasks A and B are treated as a task pair, and the final satisfaction of the required allocation is: ABXXABXXABXXAB, and the remaining tasks are interspersed without violating the required interval. The position can be separated, and the vacant position is complemented by idle. From the above analysis we can get the final task time that requires the least: Ans = (maximum number of tasks - 1) * (n + 1) + (number of tasks with the same maximum number of tasks). In the above example, it is: (num(A)-1) * (3+1) + (2). But there is another situation where ans will ans, which means that there are no tasks scheduled, so let's judge len(tasks) And the ans calculated in this way, which one is larger As for why, it seems that there is proof to prove it, but I didn’t understand it. ''' counter = [0] * 26 for task in tasks: counter[ord(task) - ord('A')] += 1 max_num = 0 max_need = max(counter) for count in counter: if count == max_need: max_num += 1 return max(len(tasks), (max_need - 1) * (n + 1) + max_num)