JavaScript

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

Вот ссылка на упражнение https://leetcode.com/problems/task-scheduler/

Читаем описание

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.

Вот пример возврата

Пример 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.

Пример 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.

Как всегда, есть разные способы решить это упражнение, здесь я просто покажу один из них.

Давайте сначала проанализируем проблему.

  1. Мы получаем массив символов. каждая буква - это задача.
  2. n представляет количество пробелов, необходимых между повторяющимися буквами.
  3. Нам нужно найти минимальное значение ..

Возьмем первый пример и проанализируем его.

Tasks = [A,A,A,B,B,B]

если n = 0, это означает, что интервал между повторяющимися буквами равен 0, и в этом случае ответ равен длине массива (пример 2).

если n = 2, результат 8, но почему?

A -> B -> idle -> A -> B -> idle -> A -> B => length equal to 8

Давайте посмотрим на массив

A B
A B
A B

у нас есть 3 группы AB, однако, поскольку n = 2, нам нужно добавить свободное пространство между двумя первыми строками

A B idle
A B idle
A B

Теперь у нас есть 2 строки длиной 3 и одна длиной 2. Теперь общее количество элементов равно 8. Вот и наш ответ.

A B idle --> length 3
A B idle --> length 3
A B      --> length 2
2 rows * 3 + 1 row * 2

Прежде чем обобщать, давайте посмотрим на другой пример.

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"]
n = 2
Output: 16
A  B    C --> length 3
A  D    E --> length 3
A  F    G --> length 3
A  idle idle --> length 3
A  idle idle --> length 3
A --> length 1
5 rows * 3 + 1 row * 1 => 16
note: as n is 2 we need two letters between two A

А теперь сделаем несколько обобщений.

* Maximum number of rows is equal to the most repeated task (or letter)
* The length of the rows - 1 is equal to the repeated letter plus the number of spaces required (n), that means the value of the length is equal n+1 
* We need to sum the length of the last row

Теперь у нас есть небольшая формула, чтобы получить нужный нам ответ.

(TotalRows - 1) * (n+1) + lastRowLength

Давайте код

  1. Получите частоты каждой буквы.
  2. Получите максимальное значение частот.
  3. Получите длину минимума

Заявление об ограничении ответственности: я собираюсь использовать javascript для кодирования ответа.

Самый простой способ получить частоты - использовать функцию редуктора. Мы создаем карту и добавляем ее каждый раз, когда появляется буква

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

const newMap = tasks.reduce((map, obj)=> {
    map[obj] = map[obj] + 1 || 1 ;
    return map;
}, {});
// the result is an object like this {A:3,B:3}

Теперь давайте получим массив значений.

const array=Object.values(newMap)
// the result is an array [3,3]

Теперь, когда у нас есть частоты, давайте получим максимальное количество частот, которое эквивалентно максимальному количеству строк.

const maximumRows = Math.max(...array) 
// result = 3

Теперь нам нужна длина последнего ряда. Для этого воспользуемся фильтром и получим длину результирующего массива.

const lastRowLength = array.filter(x => x == maximumRows).length
// result 2

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

[A,A,A,B,B,B]
frequencies -> [3,3]
Max -> 3
* How many 3 do we have in the array? -> 2 
that's the length of the last line
A B idle -> length 3
A B idle -> length 3
A B      -> length 2

Теперь результат просто

(maximumRows - 1) * (n + 1) + lastRowLength
// result 8

Теперь мы почти закончили, но помните, что у нас есть случай, когда n может быть 0, и нам нужно с ним столкнуться.

Есть две возможности, которые вы можете создать: создать условное выражение или использовать функцию max.

if (n===0) return tasks.length
or
Math.max(tasks.length, (maximumRows - 1) * (n + 1) + minimumRows)

Окончательный код может быть…

const leastInterval = (tasks, n)=> {
 const newMap = tasks.reduce((map, obj)=> {
    map[obj] = map[obj] + 1 || 1 ;
    return map;
  }, {});
     
const array=Object.values(newMap)
const maximumRows = Math.max(...array)
const lastRowLength = array.filter(x => x === maximumRows).length
return Math.max(tasks.length, (maximumRows - 1) * (n + 1) + lastRowLength) 
};

Надеюсь, вам понравилось.

Продолжайте кодировать!