621. Task Scheduler

Posted on 4 mins read

1. Description

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.
Return the least number of units of times that the CPU will take to finish all the given tasks.

2. Example

Example 1:
Input: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:
Input: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
[“A”,“A”,“A”,“B”,“B”,“B”]
[“A”,“B”,“A”,“B”,“A”,“B”]
[“B”,“B”,“B”,“A”,“A”,“A”]
…
And so on.

Example 3:
Input: tasks = [“A”,“A”,“A”,“A”,“A”,“A”,“B”,“C”,“D”,“E”,“F”,“G”], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

3. Constraints

  • 1 <= task.length <= $10^4$
  • tasks[i] is upper-case English letter.
  • The integer n is in the range [0, 100].

4. Solutions

My Accepted Solution

n = result
Time complexity: O(n)
Space complexity: O(1)

class Solution 
{
public:
    // int leastInterval(vector<char>& tasks, int n)
    int leastInterval(vector<char> &i_tasks, int interval) 
    {
        vector<int> taskTimes(26); // 26 uppercase letters, or tasks' kinds
        for(int i = 0; i < i_tasks.size(); i++)
            taskTimes[i_tasks[i] - 'A']++;
        
        int result = 0;
        sort(taskTimes.begin(), taskTimes.end(), [](int left, int right){return left > right;});
        while(taskTimes.front() > 0)
        {
            for(int i = 0; i <= interval; i++)
            {
                if(taskTimes.front() == 0) break;
                
                if(i < taskTimes.size() && taskTimes[i] > 0)
                    taskTimes[i]--;
                
                result++;
            }
            
            sort(taskTimes.begin(), taskTimes.end(), [](int left, int right){return left > right;});
        }
        
        return result;
    }
};

4.1 Priority Queue

n = result
Time complexity: O(n)
Space complexity: O(1)

class Solution 
{
public:
    // int leastInterval(vector<char>& tasks, int n)
    int leastInterval(vector<char> &i_tasks, int interval)
    {
        vector<int> taskTimes(26); // 26 uppercase letters, or tasks' kinds
        for(int i = 0; i < i_tasks.size(); i++)
            taskTimes[i_tasks[i] - 'A']++;
        
        priority_queue<int> mostOccurTasks;
        for(int i = 0; i < taskTimes.size(); i++)
        {
            if(taskTimes[i] > 0)
                mostOccurTasks.push(taskTimes[i]);
        }
        
        int result = 0;
        while(!mostOccurTasks.empty())
        {
            int time = 0;
            vector<int> temp;
            
            for(int i = 0; i <= interval; i++)
            {
                if(!mostOccurTasks.empty())
                {
                    temp.push_back(mostOccurTasks.top());
                    mostOccurTasks.pop();
                    time++;
                }
            }
            
            for(auto times : temp)
            {
                if(--times > 0)
                {
                    mostOccurTasks.push(times);
                }
            }
            
            result += (!mostOccurTasks.empty() ? interval + 1 : time);
        }
        
        return result;
    }
};

4.2 Greedy

n = i_tasks.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution 
{
public:
    // int leastInterval(vector<char>& tasks, int n)
    int leastInterval(vector<char> &i_tasks, int interval)  
    {
        vector<int> taskTimes(26); // 26 uppercase letters, or tasks' kinds
        for(int i = 0; i < i_tasks.size(); i++)
            taskTimes[i_tasks[i] - 'A']++;
        
        int mostTime = *max_element(taskTimes.begin(), taskTimes.end());
        
        // if 'A' is the task, which occurs most times, we need (mostTime - 1) * (interval + 1) times to hold it except the last one
        // then, tasks occuring times less than 'A' has been inserted into the interval between 'A'
        // we only need to find how many tasks having the same times as 'A'
        int result = (mostTime - 1) * (interval + 1);
        result += count_if(taskTimes.begin(), taskTimes.end(), [mostTime](int times){return times == mostTime;});
        
        // but this result is a lower bound
        // that's because, the most frequent task may not last until the last interval
        // it may end before the last interval, which measn we have enough space to hold tasks
        // such as [A, B, C, D, E, F], while the interval is 3
        // it is so easy to handle them, we just handle them one by one
        // but now, we need to take i_tasks.size() time
        return max((int)i_tasks.size(), result);
    }
};
comments powered by Disqus