LeetCode每日一题(2365. Task Scheduler II)

You are given a 0-indexed array of positive integers tasks, representing tasks that need to be completed in order, where tasks[i] represents the type of the ith task.

You are also given a positive integer space, which represents the minimum number of days that must pass after the completion of a task before another task of the same type can be performed.

Each day, until all tasks have been completed, you must either:

Complete the next task from tasks, or
Take a break.
Return the minimum number of days needed to complete all tasks.

Example 1:

Input: tasks = [1,2,1,2,3,1], space = 3
Output: 9

Explanation:
One way to complete all tasks in 9 days is as follows:
Day 1: Complete the 0th task.
Day 2: Complete the 1st task.
Day 3: Take a break.
Day 4: Take a break.
Day 5: Complete the 2nd task.
Day 6: Complete the 3rd task.
Day 7: Take a break.
Day 8: Complete the 4th task.
Day 9: Complete the 5th task.
It can be shown that the tasks cannot be completed in less than 9 days.

Example 2:

Input: tasks = [5,8,8,5], space = 2
Output: 6

Explanation:
One way to complete all tasks in 6 days is as follows:
Day 1: Complete the 0th task.
Day 2: Complete the 1st task.
Day 3: Take a break.
Day 4: Take a break.
Day 5: Complete the 2nd task.
Day 6: Complete the 3rd task.
It can be shown that the tasks cannot be completed in less than 6 days.

Constraints:

• 1 <= tasks.length <= 105
• 1 <= tasks[i] <= 109
• 1 <= space <= tasks.length

用一个 map 保存每种类型 task 最后一次完成的日期， 每次从 tasks 里拿取一个 task，检查该类型 task 的最后完成日期， 如果当前日期与最后完成日期的差值小于 space 则需要进行等待，反之则完成该 task， 无论那种情况当前日期都要向前推进， 前者推进到能完成的那一天的后一天， 后者直接推进一天

use std::collections::HashMap;

impl Solution {
    pub fn task_scheduler_ii(tasks: Vec<i32>, space: i32) -> i64 {
        let mut curr = 0i64;
        let mut last_days = HashMap::new();
        for t in tasks {
            if let Some(last_day) = last_days.get_mut(&t) {
                while curr - *last_day <= space as i64 {
                    curr += 1;
                    continue;
                }
                *last_day = curr;
                curr += 1;
                continue;
            }
            last_days.insert(t, curr);
            curr += 1;
        }
        curr
    }
}