621. Task Scheduler

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 thoughts on “621. Task Scheduler”

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

  2. 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

Your email address will not be published. Required fields are marked *