621. Task Scheduler

Posted on | Edited on | In , |

题目

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

想法

第一眼，感觉是Greedy

算了，想了半天，还是没有什么头绪
看答案吧

（LeetCode有答案好，也不好orz）

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        std::unordered_map<char, int> map;
        int count = 0;
        for (auto t : tasks) {
            map[t]++;
            count = max(count, map[t]);
        }
        
        int num = (n + 1) * (count - 1);
        for (auto t : map) {
            if (t.second == count)
                num++;
        }
        
        return max((int)tasks.size(), num);
    }
};

回顾

自己本来的思路跟这个类似，就选择这个作为答案了
先找到最大的，然后拉一个框：(n+1)*(count-1),如果有超出的（最大的），刚+1
另外还要考虑task大，n小，框框放不下的情况，这样需要max(task.size(), num)