【Leetcode】621.Task Scheduler

发表于 | | 阅读次数

Description

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

Input: tasks = [‘A’,’A’,’A’,’B’,’B’,’B’], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note

1.The number of tasks is in the range [1, 10000].
2.The integer n is in the range [0, 100].

Solution

First

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public int leastInterval(char[] tasks, int n) {
        if (tasks.length > 10000 || n > 100) {
            return 0;
        }
        Arrays.sort(tasks);
        int maxLength = (tasks.length - 1) * (n + 1) + 1;
        int[] max = new int[maxLength];
        for (int i = 0; i < maxLength; i++) {
            max[i] = 0;
        }
        int[] convert = new int[tasks.length];
        for (int i = 0; i < convert.length; i++) {
            convert[i] = tasks[i] - 64;
        }
        for (int i = 0; i < convert.length; i++) {
            if (i == 0) {
                max[i] = convert[i];
            } else {
                for (int j = 1; j < max.length; j++) {
                    if (max[j] != 0) {
                        continue;
                    }
                    int index = j - n > 0 ? j - n : 0;
                    int k = index;
                    for (; k < j + n + 1 && k < max.length;) {
                        if (max[k] != 0 && max[k] == convert[i]) {
                            break;
                        } else {
                            k++;
                        }
                    }
                    if (k == j + n + 1 || k == maxLength) {
                        max[j] = convert[i];
                        break;
                    }
                }
            }
        }
        int validLength = max.length;
        for (int i = max.length - 1; i >= 0; i--) {
            if (max[i] == 0) {
                validLength--;
            } else {
                break;
            }
        }
        return validLength;
    }

Result

WA

Analyse

想不到合适的方法，用的brute force，复杂度撑到了O(n^3)，显然不理想。跑过了题目提供的测试用例之后发现一个很长的字符串不过，也只有17/64的测试用例跑通，遂放弃这个方法。

Last

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public  int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1);
        }
        PriorityQueue<Map.Entry<Character, Integer>> que = new PriorityQueue<>(
                (a, b) -> a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey() - b.getKey()
        );
        que.addAll(map.entrySet());
        int count = 0;
        while (!que.isEmpty()) {
            int k = n + 1;
            List<Map.Entry<Character,  Integer>> list = new ArrayList<>();
            while (k > 0 && !que.isEmpty()) {
                Map.Entry<Character, Integer> m = que.poll();
                m.setValue(m.getValue() - 1);
                list.add(m);
                k--;
                count++;
            }
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i).getValue() > 0) {
                    que.add(list.get(i));
                }
            }
            if (que.isEmpty()) {
                break;
            }
            count = count + k;
        }
        return count;
    }

Result

AC

Analyse

思路借鉴了网上参考的内容，不过最后也是自己盲写一遍AC。开始自己一直在思考怎么使用动态规划的方法来进行求解，其实本题目可以用贪心算法，即每次做到局部最优就可以达到理想结果。

Step1

初始化2个数据结构，Map用来存储(key, value)是char和对应出现次数的映射；PriorityQueue优先队列来存储这个map的元素，制定了如下规则：1.个数最大的char存储在第一位，2.如果个数相同，正常排序在前面的char存储在前面。

Step2

例如我们有以下的情况，tasks = [‘A’,’A’,’A’,’B’,’B’,’B’,’C’,’C’,’C’]，n=2，我们直接可以看出可以按照ABCABCABC来存储满足要求。这里背后的思路是这样的：
1.我们可以考虑如果n在够大的情况下，这里说的足够大就是说，n比字母种类大，这种情况肯定是在(n+1)的长度空间里，已有种类的char每一个放入一个(n+1)空间里，还有剩余空间，但是这些剩余的空间由于n间隔的原因已经不能放入值，只能空着，再进行下一个(n+1)的存放，但是这个时候已经放完了一轮。
2.在n不够大的情况下，不够大的意思是说，n比字母种类小，这种情况肯定是想一遍放完所有种类的char是不可能做到的，我们每次通过PriorityQueuel将第一个存储个数最大的poll出来，然后将poll出来的map对应的value减去1，这样代表着我已经把这个char拿出一个按照顺序放入了这个(n+1)空间，把这一轮poll出来的map对应的value都减去1之后再存放回PriorityQueue，这样自动又是出现最多次的char在最前面，按照贪心的算法，如果减去了一次之后，PriorityQueue第一个的map的key没有变，还是那个char，这样下一次存放刚好满足，两个相同的char间隔；如果减去了这次之后，PriorityQueue第一个的map的key变了，那更不会违背题目关于相同字母的要求。

Step3

每次计数的时外面的条件是while这个PriorityQueue不为空，然后在里面每次一轮减去一个，在PriorityQueue poll的情况下，用一个List存放这些poll的内容，最后这轮之后，减去这次的使用一次情况，下一轮PriorityQueue也更新了。

Step4

假设走到了最后的情况下，当然是说PriorityQueue已经为空，那就直接break，不用计算这次的k值，因为k值存储的是(n+1)即这一轮最长的路，而count每次++都是能存的新数字，最后一轮当然只计算存放的数字。

Summary

这个解法的复杂度还是O(n^2)，看到网上有人用了一个数学解法，还是po在这里吧，但是我觉得这个解法要在面试的时候想出来确实很难，数学解法可以保证O(n)的复杂度，差不多是13ms和213ms的差距，确实感觉到算法的重要性，复杂度太大的解法是灾难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int _leastInterval_(char[] tasks, int n) {
        //思路不容易想起来，因为有数学的思路
        int[] test = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            test[tasks[i] - 'A']++;
        }
        Arrays.sort(test);
        int count = 0;
        int len = test.length - 1;
        while (test[len] == test[--len]) {
            count++;
        }
        return Math.max(tasks.length,(test[25] - 1) * (n + 1) + count + 1);
    }

Analyse

这里也分析一下这个思路，这个思路其实和我提交的思路是一致的，不过我是保证每轮最优，这个有一种把这所有轮一起提纲挈领的感觉。
按照数组存储之后排序，首先当做n很大，然后将个数最大的那个数字来排，不算最后一轮，那就是(test[25]-1)*(n+1)，这已经是除去最后一轮的长度了，这个时候想，其实剩下的最后一轮只有和个数最大那个数一样大的剩下了，那就是前面的while找出的(count+1)，即就是看你还有几个剩下的一起排；如果当做n很小的话，那当然就是tasks.length可以直接存储了，这个思路完全没毛病。
很少用贪心算法解题，其实贪心算法能做出全局最优的解法也不那么多，还是好好总结吧。

坚持原创技术分享，您的支持将鼓励我继续创作！