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))