Task Schedule with Original Order

https://weirenwang1.gitbooks.io/algorithm/fb-rearrange-string-k-distance-apart.html

给定任务AABCB, 冷却时间k（相同任务之间的最短距离时间），任务顺序不能变，问完成任务的总时间。

例子：AABCB, k = 3, A _ _ A B C _ B, 时间为8.

解法：用hashtable保存上次的时间。

Followup1：如果k很小，怎么优化？ 解法：之前的hashtable的大小是unique task的大小，如果k很小，可以只维护k那么大的hashtable

给一个String, 如AABACCDCD, 插入''使同一个字母间隔为k: 如果k=3: A - - - A B - - A C - - - C D - - C D,

Thoughts

遍历, 与上次该字母的所在位置进行比较, 因此需要一个map不断保存每个字母最后出现的位置.

Code

public String schedule(String str, int n) {
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> pos = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (!pos.containsKey(c)) {
                sb.append(c);
            } else {
                while ((sb.length() - pos.get(c)) <= n) {
                    sb.append('_');
                }
                sb.append(c);
            }
            pos.put(c, sb.length() - 1);
        }

        return sb.toString();
    }

Analysis

时间复杂度O(N).

Ver.2

只需要返回长度.

public static int schedule2(String str, int n) {
        int pos = 0;
        Map<Character, Integer> locs = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (locs.containsKey(c) && pos - locs.get(c) <= n) {
                pos += locs.get(c) + n - pos + 1;
            }

            locs.put(c, pos++);
        }

        return pos;
    }