TaskCooldown

题目地址：https://instant.1point3acres.com/thread/195147


题目：
Task那道题，很多面经都提到过。就是比如给你一串task，再给一个cooldown，执行每个task需要时间1，两个相同task之间必须至少相距cooldown的时间，问执行所有task总共需要多少时间。比如执行如下task：12323，假设cooldown是3。总共需要的时间应该是 1 2 3 _ _ 2 3，也就是7个单位的时间。再比如 1242353，假设cool down是4，那总共时间就是 1 2 4 _ _ _ 2 3 5 _ _ _ 3，也就是13个单位的时间

解题思路：
首先定义两个变量：time和prev_time。第一个表示当前任务执行的时间，第二个表示该任务之前出现的时间。这道题需要用一个map来存储之前出现的时间。只有当time <= prev_time + cooldown + 1 的时候才需要更新time。之后把char和更新后的time放到map里面就好。


代码：

public static int min_time(int[] tasks, int interval){
    if(tasks == null || tasks.length == 0){
        return 0;
    }
    Map map = new HashMap();
    int time = 0;
    for(int task : tasks){
        Integer task_last_time = (Integer) map.get(task);
        if(task_last_time != null && task_last_time + interval + 1 > time){
            time = task_last_time + interval + 1;
        }
        map.put(task, time);
        time++;
    }
    return time;
}
public static void main(String[] args){
    int[] tasks1 = {1, 2,3,2,3};
    System.out.println(min_time(tasks1, 3));

    int[] tasks2 = {1, 2, 4, 2, 3, 5, 3};
    System.out.println(min_time(tasks2, 4));
}

另外一种思路：
map存的是task with id [i] 下一个可以进行的index。(更好理解)

代码：

public class TaskCooldown {

    public int schedule(int[] tasks, int cooldown){
        if(tasks == null || tasks.length == 0){
            return 0;
        }
        if(tasks.length == 1){
            return 1;
        }
        int rst = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i <= tasks.length - 1; i++){
            if(!map.containsKey(tasks[i])){
                rst += 1;
                map.put(tasks[i], rst + cooldown + 1);
            }
            else{
                int available = map.get(tasks[i]);
                rst += 1;
                if(rst >= available){
                    // could fill int position rst                    map.put(tasks[i], rst + cooldown + 1);
                }
                else{
                    rst = available;
                    map.put(tasks[i], rst + cooldown + 1);
                }
            }
        }
        return rst;
    }

    public static void main(String[] args){
        TaskCooldown taskCooldown = new TaskCooldown();
        int[] tasks1 = {1, 1, 2, 1};
        int[] tasks2 = {1, 2, 1, 1};
        int rst1 = taskCooldown.schedule(tasks1, 2);
        int rst2 = taskCooldown.schedule(tasks2, 2);
        System.out.println(rst1);
        System.out.println(rst2);
    }

}