**Description:**

https://leetcode.com/problems/task-scheduler/description/

**Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: int leastInterval(vector<char>& tasks, int n) { int taskNum = tasks.size(); vector<int> table = vector<int>(26, 0); for (int i = 0; i < taskNum; i++) { table[tasks[i] - 'A']++; } sort(table.begin(), table.end()); int rowNum = table[25] - 1; int idleNum = rowNum * n; for (int i = 0; i < 25; i++) { idleNum -= min(table[i], rowNum); } return idleNum < 0 ? taskNum : idleNum + taskNum; } }; |

**Time & Space:**

Record: O(1)

Sort: O(nlogn)

Calculate idle: O(1)

Space: O(1)

There is no need to sort.

O(N)

class Solution {

public:

// O(n) greedy

int leastInterval(vector& tasks, int n) {

vector table(26, 0);

for (const auto &task : tasks)

++table[int(task – ‘A’)];

int maximum = *std::max_element(table.begin(), table.end());

// number of threads without the maximum

int ans = (maximum – 1) * (n + 1);

// add the maximum in the end

for (const auto &num : table)

if (num == maximum)

++ans;

return max(ans, (int)tasks.size());

}

};

Cool!

`python`

class Solution:

def leastInterval(self, tasks, n):

table = [0] * 26

for task in tasks:

table[ord(task) - 65] += 1

maximum = max(table)

ans = (maximum - 1) * (n + 1)

for num in table:

if num == maximum:

ans += 1

return max(ans, len(tasks))