2365. Task Scheduler II

📝 Problem Details

• Title: 2365. Task Scheduler
• Link: https://leetcode.com/problems/task-scheduler-ii/
• Difficulty: Medium
• Tags/Categories: Arrays Hashmap

💭What Were My Initial Thoughts?

- the order of task execution has to be maintained, sorting the array is not an option
- we can use a hashmap to keep track of a task and the last day it occurred on

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- use a hashmap to track that last day each task type was executed at
	- key: the task type (from tasks vector)
	- value: last day the task was executed

- for each task, check the last execution day stored in the hashmap
	- if the task has been executed before, calculate when it can be executed again
	- if the current day if less than the required execution day, skip to the earliest allowable day for this task
- update the current day and record the task's execution 

⌛ Complexity Analysis

Time Compelxity: O(n)
Space Complexity: 
	O(n) for the use of the hashmap
	also considered to be O(u) where U is the number of unique tasks in the input vector

💻 Implementation of Solution

class Solution {
public:
    int taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<long long, long long> taskLastDay; // Store the last execution day for each task
        long long currentDay = 0; // Use long long to handle large inputs
 
        for (int task : tasks) {
            // Increment the current day for each iteration (base day counter)
            currentDay++;
            
            // Check if the task has been executed before
            if (taskLastDay.find(task) != taskLastDay.end()) {
                long long lastDay = taskLastDay[task];
                // If within cooldown, adjust currentDay
                if (currentDay <= lastDay + space) {
                    currentDay = lastDay + space + 1;
                }
            }
            
            // Update the last execution day for this task
            taskLastDay[task] = currentDay;
        }
 
        // Return the total number of days
        return currentDay;
    }
};