Solution For Task Scheduler

Problem Statement:

You are given a list of tasks that need to be executed, each with a fixed start time and duration. Given a non-negative integer n that represents the cooldown period between two tasks of the same type, return the minimum number of CPU intervals needed to execute all the given tasks.

Example:

Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2

Output: 8

Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B

Approach:

To solve this problem, we can use a greedy approach. First, we need to count the frequency of each task. Then, we sort the tasks in decreasing order of their frequency. We also maintain a list of cooldowns for each task. Initially, all the cooldowns are 0.

We start processing the tasks in the order of their frequency. For each task, we find the task with the maximum cooldown. If the maximum cooldown is greater than 0, we wait for that many intervals before processing the current task. If the maximum cooldown is 0, we can process the current task immediately.

After processing the current task, we update the cooldown of all the tasks. The cooldown of the current task is set to n+1 (n is the given cooldown period). This is because we need to leave a gap of n intervals before processing the same task again. The cooldown of all the other tasks is reduced by 1.

We repeat this process until all the tasks are processed.

Code:

class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> freq;
for (char t : tasks) {
freq[t]++;
}
auto cmp = [&](char a, char b) {
return freq[a] < freq[b];
};
priority_queue<char, vector<char>, decltype(cmp)> pq(cmp);
for (auto p : freq) {
pq.push(p.first);
}
vector<int> cooldown(26, 0);
int intervals = 0;
while (!pq.empty()) {
vector<char> available;
while (!pq.empty()) {
char t = pq.top();
pq.pop();
if (cooldown[t-'A'] == 0) {
available.push_back(t);
break;
}
}
if (available.empty()) {
intervals++;
} else {
char t = available.front();
available.erase(available.begin());
freq[t]--;
cooldown[t-'A'] = n+1;
for (char c : available) {
cooldown[c-'A']--;
}
if (freq[t] > 0) {
pq.push(t);
}
intervals++;
}
for (int i = 0; i < 26; i++) {
if (cooldown[i] > 0) {
cooldown[i]--;
}
}
}
return intervals;
}
};

Time Complexity:

The time complexity of this solution is O(nlogn), where n is the number of tasks. The sorting of tasks takes O(nlogn) time, and for each task, we can spend at most O(logn) time in the priority queue. Since we process each task exactly once, the total time complexity is O(nlogn).

Step by Step Implementation For Task Scheduler

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int max_val = map[25] - 1, idle_slots = max_val * n;
        for (int i = 24; i >= 0 && map[i] > 0; i--) {
            idle_slots -= Math.min(map[i], max_val);
        }
        return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
    }
}

There are a total of n tasks you have to pick, labeled from 0 to n-1. Some tasks may have dependencies, i.e. they need to be done before others. 

Given the number of tasks and a list of dependencies, return a sequence of tasks you need to pick to finish all tasks.

You may assume that there will be no circular dependencies.

 

Example 1:

Input: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 tasks. You can do them in any order, but you should make sure to do task 0 first.

def findOrder(numCourses, prerequisites):

    #Create a graph and add edges
    graph = collections.defaultdict(list)
    for u, v in prerequisites:
        graph[u].append(v)

    #Create a visited set to keep track of visited nodes
    visited = set()

    #Create a stack to keep track of the order of nodes
    stack = []

    #Create a function to do a depth first search
    def dfs(node):
        if node in visited:
            return False
        visited.add(node)
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        stack.append(node)
        return True

    #Do a depth first search for all nodes
    for i in range(numCourses):
        if not dfs(i):
            return []
    return stack[::-1]

var leastInterval = function(tasks, n) {
    // create a hashmap to store the count of each task
    let map = {};
    for(let t of tasks){
        map[t] = (map[t]||0) + 1;
    }
    // sort the tasks according to their count in descending order
    let sortable = [];
    for(let t in map){
        sortable.push([t, map[t]]);
    }
    sortable.sort((a,b) => {
        return b[1] - a[1];
    });
    // find the maximum count
    let maxCount = sortable[0][1];
    // find the number of tasks with maximum count
    let maxTasks = 0;
    for(let i = 0; i < sortable.length; i++){
        if(sortable[i][1] == maxCount){
            maxTasks++;
        }
    }
    // the minimum number of intervals needed is equal to the maximum count of any task plus the number of tasks with that maximum count minus 1, all multiplied by n plus 1
    return Math.max((maxCount - 1) * (n + 1) + maxTasks, tasks.length);
};

class Solution {
public:
    int leastInterval(vector& tasks, int n) {
        // Create a map of task counts
        unordered_map taskCounts;
        for (char c : tasks) {
            taskCounts[c]++;
        }
        
        // Sort the task counts in descending order
        priority_queue pq;
        for (auto it : taskCounts) {
            pq.push(it.second);
        }
        
        // Perform the scheduling
        int intervalCount = 0;
        while (!pq.empty()) {
            // Schedule up to n tasks at a time
            vector scheduledTasks;
            for (int i = 0; i <= n; i++) {
                if (!pq.empty()) {
                    scheduledTasks.push_back(pq.top());
                    pq.pop();
                }
            }
            
            // Add the scheduled tasks back to the queue
            for (int count : scheduledTasks) {
                if (--count > 0) {
                    pq.push(count);
                }
            }
            
            // Add n+1 to the interval count (if there are more tasks to schedule)
            // or add the number of scheduled tasks (if there are no more tasks to schedule)
            intervalCount += pq.empty() ? scheduledTasks.size() : n + 1;
        }
        
        return intervalCount;
    }
};

public class Solution {
    public int LeastInterval(char[] tasks, int n) {
        // Create a frequency map of all the tasks
        var taskFrequencyMap = new Dictionary();
        foreach(var task in tasks)
        {
            if(taskFrequencyMap.ContainsKey(task))
            {
                taskFrequencyMap[task]++;
            }
            else
            {
                taskFrequencyMap.Add(task, 1);
            }
        }
        
        // Sort the tasks by frequency (most frequent first)
        var sortedTasks = taskFrequencyMap.OrderByDescending(t => t.Value).Select(t => t.Key).ToList();
        
        // Initialize the result
        var result = 0;
        
        // Loop through the tasks
        while(sortedTasks.Count > 0)
        {
            // Initialize the current task list
            var currentTasks = new List();
            
            // Add the most frequent task to the current task list
            currentTasks.Add(sortedTasks[0]);
            
            // Remove the most frequent task from the sorted task list
            sortedTasks.RemoveAt(0);
            
            // Loop through the remaining tasks
            for(int i = 0; i < sortedTasks.Count; i++)
            {
                // If the current task list is not full
                if(currentTasks.Count < n + 1)
                {
                    // Add the next task to the current task list
                    currentTasks.Add(sortedTasks[i]);
                    
                    // Remove the task from the sorted task list
                    sortedTasks.RemoveAt(i);
                    
                    // Decrement the index so that we don't skip a task
                    i--;
                }
                else
                {
                    // Break out of the loop, we don't need to process any more tasks
                    break;
                }
            }
            
            // If the sorted task list is empty, we can just return the result
            if(sortedTasks.Count == 0)
            {
                return result + currentTasks.Count;
            }
            
            // Otherwise, we need to update the frequencies of the tasks that we processed
            foreach(var task in currentTasks)
            {
                taskFrequencyMap[task]--;
            }
            
            // Add the current task list count to the result
            result += currentTasks.Count;
            
            // Sort the tasks by frequency (most frequent first)
            sortedTasks = taskFrequencyMap.Where(t => t.Value > 0).OrderByDescending(t => t.Value).Select(t => t.Key).ToList();
        }
        
        return result;
    }
}