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

Code:

 

Time & Space:
Record: O(1)
Sort: O(nlogn)
Calculate idle: O(1)

Space: O(1)

3 comments

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

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

Leave a Reply

*