Task Scheduler - LeetCode Challenge

Question

I was attempting to solve this problem

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1: Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

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

The greedy criteria I came up with is, for scheduling a particular task optimally with minimum empty slots we pick the highest occurring task and maintain maximum number of distinct tasks at each stage.

Algoritm :

1. Load the task by it's occurrence in a queue
2. While the number of distinct tasks is greater than the cool period we pick the cool number of tasks with highest occurrence and decrease it by 1.
3. If the number of distinct tasks is less that the cool period then we multiply cool period with the highest occurrence of the task.

The code is below.

template<typename T> int CountLastTask(T& queue, int n) 
{
    int count = 0;
    while(!queue.empty() && queue.top().first == n) {
        ++count;
        queue.pop();        
    }
    return count;
}

struct compare
{
    bool operator()(const pair<int, char> left, const pair<int, char> right)
    {
        return left.first < right.first;
    }
};
int leastInterval(vector<char>& input, int cool) 
{
    map<char, int> values;
    for(auto c : input)
    {
        values[c] += 1;
    }
    int answer = 0;
    priority_queue<pair<int, char>, vector<pair<int, char>>, compare> queue;      
    for(auto c: values)
    {
        queue.push({c.second, c.first});
    }
    while(queue.size() > 0)
    {
        auto top = queue.top();

        if(queue.size() < cool + 1)
        {
            int last_task = CountLastTask(queue, top.first);
            answer += ((top.first - 1) * (cool + 1)) + last_task;
            return answer;
        }
        int index = 0;
        vector<pair<int, int>> history;
        while(index < cool + 1)
        {
            top = queue.top();
            if(top.first > 1)
            {
                history.push_back({top.first -1, top.second});    
            }
            queue.pop();
            ++index;
        }
        for(auto it : history)
        {
            queue.push(it);
        }
        answer += cool + 1;
    }
    return answer;
}

I am not sure if my solution uses the right data structure in the correct way. As inserting back into the queue requires me to store the pop-ed values in an temporary array and then insert it back.

Could you review this code for the right usage of data structures.

Answer 1

First the nitty picky stuff

1. Every container has a empty() method. I would consider it bad practice to use size() > 0 rather than !empty(), as it can have really performance implictations for lists and maps.

2. Please post complete code. You are missing any headers and also the dubious using namespace std; That one you should really ommit in your code and start using proper namespaces.

So now to the problem at hand. I think your data structure is indeed badly choosen. The first thing to note is what is important.

a. The type of instruction
b. The number of remaining instructions
c. The time until a certain instruction is ready.

You are missing the third point, which complicates the code more than it should. So lets start with a data structure that fits the problem

struct Instruction {
    Instruction(const char id)
        : Identifier(id)
    {}

    const char Identifier;
    size_t remainingUses = 1;
    size_t nextPossibleTime = 0;
}

So I named it next possible time, because the current time since start is the same for every instruction. Now given a current time we can schedule an instruction

char scheduleInstruction(const size_t currentTime, const size_t coolDown) {
    --remainingUses;
    nextPossibleTime = currentTime + coolDown + 1;
    return Identifier;
}

So when we schedule an instruction we decrement the number of remaining uses and set the next possible instruction time until the current time + the cool down period. Obviously we can put currentTime+coolDown+1 in the caller but that is a question of personal preference.

Now to check whether an Instruction can be scheduled we only have to compare currentTime with nextPossibleTime for the instruction.

So now we have scheduled an instruction how do we move it withine a queue? Quite easy there are only 2 relevant quantities

1. nextPossibleTime
2. remainingUses

So lets define a comparison operator for that task as you did

inline bool
operator< (Instruction const& b) const {
    return std::tie(nextPossibleTime, remainingUses) < 
           std::tie(b.nextPossibleTime, b.remainingUses);
}

By using std::tie we automatically get the correct comparison of the two fields. Now consider a given container and we have scheduled an instruction, then we swap the elements until our scheduled instruction is not smaller than
another given instruction.

void rescheduleInstructions() {
    auto lastInstruction = myInstructions.rbegin();
    auto nextInstruction = std::next(lastInstruction, 1);

    while(nextInstruction != myInstructions.rend() && (*lastInstruction< *nextInstruction) {
        std::iter_swap(nextInstruction , lastInstruction);
        ++nextInstruction;
        ++lastInstruction;
    }
}

EDIT:

So I made a mistake here. The problem becomes obvious when looking at the simple sequence AAABC n=2

The A Instruction will be scheduled after B and C with the old code, leading to the sequence

A->B->C->A->Idle->A

However the optial sequence would be

A->B->A->C->A

The reason for the error is, that we only need go back at max coolDown steps as after that point any instruction will be ready and we can sort from there with simply after the remainingUses, which ensures that we always schedule the most important instruction first.

void rescheduleInstructions() {
    auto lastInstruction = myInstructions.rbegin();
    auto nextInstruction = std::next(lastInstruction, 1);

    for (size_t step = 0; step  < coolDown; ++step ) {
        if (nextInstruction == myInstructions.rend()) {
            break;
        }
        if (*nextInstruction < *lastInstruction) {
            break;
        }
        std::iter_swap(nextInstruction , lastInstruction);
        ++nextInstruction;
        ++lastInstruction;
    }
}

---

So lets wrap this up by creating a class for the instruction set

class InstructionSet {
    InstructionSet (const std::string instructions, const size_t cooldown)
        :coolDown(cooldown)
    {
        for (const char& instruction : instructions) {
            auto pos = std::find(myInstructions.begin(), myInstructions.end(), [&instruction](const Instruction& i) {return i.Identifier == instruction; });
            if (pos != myInstructions.end()) {
                pos->AddInstruction();
            } else {
                myInstructions.emplace_back(instruction); 
            }
        }
        std::sort(myInstructions.rbegin(), myInstructions.rend());
    }

    std::string findOptimalSchedule();

private:
    void rescheduleInstructions();

    std::container<Instruction> myInstructions;
    size_t currentTime = 1;
    const size_t coolDown;
}

You could also go for sorted insertion into the vector, however i felt that it complicates the matter of finding and in my experience just inserting and sorting at the end is more performant.

Now for the optimal schedule we have to start with the last element and then go from there. If currentTime is not less than nextPossibleTime of the final instruction we can schedule it. Otherwise due to the ordering we know that there is no possible instruction and we have to go idle (I choose "1" for that). After an instruction has been scheduled, we check whether there are remaining uses and either remove it or reschedule.

    std::string findOptimalSchedule() {
        std::string schedule;
        while(!myInstructions.empty()) {
            auto nextInstruction = myInstructions.rbegin();
            if(currentTime >= nextInstruction->nextPossibleTime) {
                schedule.push_back(nextInstruction->scheduleInstruction(currentTime, coolDown));
                if (nextInstruction->remainingUses == 0) {
                    myInstructions.erase(nextInstruction);
                } else {
                    rescheduleInstructions();
                }
            } else {
                schedule.push_back("1");
            }
            ++currentTime;
        }
        return schedule;
    }

Edit

To put all the code together and remove the unnecessary occurence of std::string although it

#include <algorithm>
#include <vector> 

struct Instruction {
    Instruction(const char id)
        : Identifier(id)
    {}

    inline bool
    operator< (Instruction const& b) const {
        return std::tie(nextPossibleTime, remainingUses) < 
               std::tie(b.nextPossibleTime, b.remainingUses);
    }

    char scheduleInstruction(const size_t currentTime, const size_t coolDown) {
        --remainingUses;
        nextPossibleTime = currentTime + coolDown + 1;
        return Identifier;
    }

    const char Identifier;
    size_t remainingUses = 1;
    size_t nextPossibleTime = 0;
}

    class InstructionSet {
    InstructionSet (const std::vector<char> instructions, const size_t cooldown)
        :coolDown(cooldown)
    {
        for (const char& instruction : instructions) {
            auto pos = std::find(myInstructions.begin(), myInstructions.end(), [&instruction](const Instruction& i) {return i.Identifier == instruction; });
            if (pos != myInstructions.end()) {
                pos->AddInstruction();
            } else {
                myInstructions.emplace_back(instruction); 
            }
        }
        std::sort(myInstructions.rbegin(), myInstructions.rend());
    }

    int findOptimalSchedule() {
        std::vector<char> schedule;
        while(!myInstructions.empty()) {
            auto nextInstruction = myInstructions.rbegin();
            if(currentTime >= nextInstruction->nextPossibleTime) {
                schedule.push_back(nextInstruction->scheduleInstruction(currentTime, coolDown));
                if (nextInstruction->remainingUses == 0) {
                    myInstructions.erase(nextInstruction);
                } else {
                    rescheduleInstructions();
                }
            } else {
                schedule.push_back('1');
            }
            ++currentTime;
        }
        return static_cast<int>(schedule.size());
    }

private:
    void rescheduleInstructions() {
        auto lastInstruction = myInstructions.rbegin();
        auto nextInstruction = std::next(lastInstruction, 1);

        for (size_t step = 0; step  < coolDown; ++step ) {
            if (nextInstruction == myInstructions.rend()) {
                break;
            }
            if (*nextInstruction < *lastInstruction) {
                break;
            }
            std::iter_swap(nextInstruction , lastInstruction);
            ++nextInstruction;
            ++lastInstruction;
        }
    }

    std::vector<Instruction> myInstructions;
    size_t currentTime = 1;
    const size_t coolDown;
}