Task Scheduler II

Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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 <= 10^5
1 <= tasks[i] <= 10^9
1 <= space <= tasks.length

Solution

Method 1 - Last Completion Mapping (Greedy)

Intuition

For each task, we check if it was last done within space days. If so, we must wait; otherwise, we can do it immediately. We update the last completion day for each task type.

Approach

We keep track of the last day each task type was completed. For each task, if it was last done more than space days ago, we can do it immediately; otherwise, we must wait until the required number of days have passed. We increment the current day accordingly.

Complexity

⏰ Time complexity: O(n) – We visit each task once and perform O(1) operations per task using a hash map.
🧺 Space complexity: O(m) – We store the last completion day for each of the m unique task types.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <unordered_map>
class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, long long> last;
        long long day = 0;
        for (int t : tasks) {
            ++day;
            if (last.count(t) && day - last[t] <= space) {
                day = last[t] + space + 1;
            }
            last[t] = day;
        }
        return day;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
package solution

func taskSchedulerII(tasks []int, space int) int64 {
    last := make(map[int]int64)
    var day int64 = 0
    for _, t := range tasks {
        day++
        if prev, ok := last[t]; ok && day-prev <= int64(space) {
            day = prev + int64(space) + 1
        }
        last[t] = day
    }
    return day
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import java.util.*;
class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        Map<Integer, Long> last = new HashMap<>();
        long day = 0;
        for (int t : tasks) {
            day++;
            if (last.containsKey(t) && day - last.get(t) <= space) {
                day = last.get(t) + space + 1;
            }
            last.put(t, day);
        }
        return day;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    fun taskSchedulerII(tasks: IntArray, space: Int): Long {
        val last = mutableMapOf<Int, Long>()
        var day = 0L
        for (t in tasks) {
            day++
            if (last.containsKey(t) && day - last[t]!! <= space) {
                day = last[t]!! + space + 1
            }
            last[t] = day
        }
        return day
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def taskSchedulerII(self, tasks: list[int], space: int) -> int:
        last: dict[int, int] = {}
        day = 0
        for t in tasks:
            day += 1
            if t in last and day - last[t] <= space:
                day = last[t] + space + 1
            last[t] = day
        return day

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
use std::collections::HashMap;
impl Solution {
    pub fn task_scheduler_ii(tasks: Vec<i32>, space: i32) -> i64 {
        let mut last: HashMap<i32, i64> = HashMap::new();
        let mut day: i64 = 0;
        for &t in &tasks {
            day += 1;
            if let Some(&prev) = last.get(&t) {
                if day - prev <= space as i64 {
                    day = prev + space as i64 + 1;
                }
            }
            last.insert(t, day);
        }
        day
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function taskSchedulerII(tasks: number[], space: number): number {
    const last = new Map<number, number>();
    let day = 0;
    for (const t of tasks) {
        day++;
        if (last.has(t) && day - last.get(t)! <= space) {
            day = last.get(t)! + space + 1;
        }
        last.set(t, day);
    }
    return day;
}

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 - Last Completion Mapping (Greedy)#

Intuition#

Approach#

Complexity#

Code#