Задача Планировщика - LeetCode Вызов


Я пытался решить эту проблему

Дан массив типа char, представляющий задач ЦП нужно сделать. Он содержит заглавные буквы от A до Z, где разные буквы обозначают разные задачи.Задач может быть сделано без первоначального заказа. Каждая задача может быть сделано через один интервал. Для каждого интервала, процессор мог бы закончить одну задачу или просто простаивает.

Тем не менее, существует неотрицательное охлаждения интервале N, что означает, между двух одинаковых задач, там должно быть как минимум N интервалов, что процессор делают различные задачи или просто простаивает.

Вам нужно вернуть наименьшее количество интервалов процессора уйдет на закончить все поставленные задачи.

Пример 1: ввод: задачи = ["А","В","А","Б","Б","б"], п = 2

Выход: 8

Объяснение: А -> Б -> режим ожидания -> А -> Б -> режим ожидания -> а -> Б.

Жадный критериям я придумал, для планирования конкретной задачи оптимально с минимальными пустые слоты мы выбираем самый высокий возникающих задач и сохранить максимальное количество различных задач на каждом этапе.

Алгоритм :

  1. Загрузить задача его появления в очереди
  2. В то время как количество различных задач больше, чем cool период мы выбираем cool количество задач с высоким возникновения и уменьшить его на 1.
  3. Если количество различных задач меньше cool период затем мы умножаем cool период с наивысшим возникновения задач.

Код ниже.

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;
}

Я не уверен, если мое решение использует правильную структуру данных в правильный путь. Как вставить в очередь, обязывает меня хранить pop-Ред значения в временный массив, а затем вставьте ее обратно.

Не могли бы вы рассмотреть этот код за право использования структур данных.



Комментарии
1 ответ

Сначала вшивый требователен вещи


  1. Каждый контейнер имеет empty() метод. Я считаю это плохая практика, чтобы использовать size() > 0 а не !empty()как он может действительно производительность implictations для списков и карт.

  2. Пожалуйста, напишите полный код. Вам не хватает каких-либо заголовков и сомнительных using namespace std; что одна ты действительно должен опустить в ваш код и запустить с помощью соответствующего пространства имен.

Так что теперь к проблеме под рукой. Я думаю, что ваша структура данных-это действительно плохо выбраны. Первое, что нужно отметить то, что важно.

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

Вам не хватает третьего пункта, который усложняет код больше, чем следовало. Итак, давайте начнем с структура данных, которая соответствует проблеме

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

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

Поэтому я назвал его ближайшее время, потому что в текущее время с момента запуска одинаков для каждой инструкции. Сейчас дали текущее время мы можем планировать обучение

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

Поэтому, когда мы планируем поручение, мы уменьшаем количество оставшихся использует и установить рядом можно инструкция время до текущего времени + период затишья. Очевидно, мы можем поставить currentTime+coolDown+1 в звонящего, но это вопрос личных предпочтений.

Теперь проверьте, есть ли инструкция может быть назначено только для сравнения currentTime С nextPossibleTime для обучения.

Так что теперь у нас есть запланированные инструкцию, как мы переместить его withine очереди? Довольно легко есть только 2 существенных объемов

1. nextPossibleTime
2. remainingUses

Это позволяет определить оператор сравнения для этой задачи, как вы делали

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

С помощью std::tie мы автоматически получаем правильное сравнение двух полей. Теперь рассмотрим данного контейнера и в инструкции, потом меняемся элементов до нашего запланированного инструкция не меньше, чем
еще дали инструкцию.

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;
}
}

Редактировать:

Так что я сделал здесь ошибку. Проблема становится очевидной при взгляде на простую последовательность
AAABC н=2

В инструкции будет назначена после B и C со старым кодом, что приводит к последовательности

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

Однако optial последовательности будет

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

Причина ошибки в том, что мы только должны вернуться на максимум coolDown шаги, как после этого любая инструкция будет готова и мы оттуда просто после remainingUsesэто гарантирует, что мы всегда планируйте самые важные инструкции первого.

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;
}
}


Так что давайте закругляться путем создания класса для набора инструкций

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;
}

Вы могли бы также пойти для вставки в отсортированный вектор, однако я чувствовал, что это усложняет дело находить и по моему опыту просто установка и сортировка в конце является более производительным.

Теперь для оптимального графика мы должны начать с последнего элемента, а затем идти оттуда. Если текущее время составляет не менее nextPossibleTime заключительного инструктажа, мы можем запланировать его. В противном случае из-за заказ мы знаем, что нет инструкции и мы должны перейти в режим ожидания (я выбрал "1" для этого). После обучения было запланировано, мы проверяем, есть ли оставшиеся использует и либо удалить его или перенести.

    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;
}

Редактировать

Чтобы поместить весь код вместе и удалить ненужную повторяемость СТД::строка, хотя это

#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;
}

2
ответ дан 12 февраля 2018 в 10:02 Источник Поделиться