Skip to content

Latest commit

 

History

History
138 lines (82 loc) · 3.6 KB

0621._Task_Scheduler.md

File metadata and controls

138 lines (82 loc) · 3.6 KB

621. Task Scheduler

难度: Medium

刷题内容

原题连接

内容描述

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.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 1:
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].

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

思路参考见jinzhou

我们只需要算我们需要多少idle，最终的结果就是len(tasks)+idles

例如3 A, 2 B, 1 C, 我们从频率最大的A开始排列，那么一定可以排成这个样子：A??A??A,其中?````代表的是还没有排列的任务， 然后此时A已经排完了，我们继续从当前最大的B开始排，就是AB?AB?A,把C也放进去，就是ABCAB?A，最终我们就只需要一个idle，因此最终结果就是 len(tasks)+idles = 6+1 = 7```

如果我们有多个频率最多的task的时候，例如，3 A, 3 B, 2 C, 1 D，那么我们其实可以将AB同时看成一个task，然后问题就一样了，

对于A ? ? ? A ? ? ? A

?所在区域就是我们的emptySlots

  • partCount = count(A) - 1
  • emptySlots = partCount * (n - (count of tasks with most frequency - 1))
  • availableTasks = tasks.length - count(A) * count of tasks with most frenquency
  • idles = max(0, emptySlots - availableTasks)
  • result = tasks.length + idles

直接按照这种格式写， beats 73.65

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        d = collections.Counter(tasks)
        part_count = max(d.values()) - 1
        empty_slots = part_count * (n-(len([i for i in d.values() if i == max(d.values())])-1))
        available_tasks = len(tasks) - len([i for i in d.values() if i == max(d.values())]) * max(d.values())
        idles = max(0, empty_slots - available_tasks)
        return len(tasks) + idles

完全可以写的更简单一点, beats 84.90%

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        lookup = {}
        for task in tasks:
            lookup[task] = lookup.get(task, 0) + 1
        max_freq = max(lookup.values())
        res = (max_freq-1) * (n+1)
        for freq in lookup.values():
            if freq == max_freq:
                res += 1
        return max(len(tasks), res)

写成两行版本吧

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        d = collections.Counter(tasks).values()
        return max((max(d)-1)*(n+1) + d.count(max(d)), len(tasks))