> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/jian-guo/task-schedule-with-original-order.md).

# 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;
    }
```