[C++] [Java] Clean Code - Priority Queue


  • 18

    The idea is:

    1. To work on the same task again, CPU has to wait for time n, therefore we can think of as if there is a cycle, of time n+1, regardless whether you schedule some other task in the cycle or not.
    2. To avoid leave the CPU with limited choice of tasks and having to sit there cooling down frequently at the end, it is critical the keep the diversity of the task pool for as long as possible.
    3. In order to do that, we should try to schedule the CPU to always try round robin between the most popular tasks at any time.

    priority_queue<task, count>

    class Solution {
    public:
        int leastInterval(vector<char>& tasks, int n) {
            unordered_map<char, int> counts;
            for (char t : tasks) {
                counts[t]++;
            }
            priority_queue<pair<int, char>> pq;
            for (pair<char, int> count : counts) {
                pq.push(make_pair(count.second, count.first));
            }
            int alltime = 0;
            int cycle = n + 1;
            while (!pq.empty()) {
                int time = 0;
                vector<pair<int, char>> tmp;
                for (int i = 0; i < cycle; i++) {
                    if (!pq.empty()) {
                        tmp.push_back(pq.top());
                        pq.pop();
                        time++;
                    }
                }
                for (auto t : tmp) {
                    if (--t.first) {
                        pq.push(t);
                    }
                }
                alltime += !pq.empty() ? cycle : time;
            }
            return alltime;
        }
    };
    

    priority_queue<count>
    As @milu point out, we don't really need to store <task - count> pair in the priority_queue, we don't need to know the task name, store counts works good enough:

    class Solution {
    public:
        int leastInterval(vector<char>& tasks, int n) {
            unordered_map<char, int> counts;
            for (char t : tasks) {
                counts[t]++;
            }
            priority_queue<int> pq;
            for (pair<char, int> count : counts) {
                pq.push(count.second);
            }
            int alltime = 0;
            int cycle = n + 1;
            while (!pq.empty()) {
                int time = 0;
                vector<int> tmp;
                for (int i = 0; i < cycle; i++) {
                    if (!pq.empty()) {
                        tmp.push_back(pq.top());
                        pq.pop();
                        time++;
                    }
                }
                for (int cnt : tmp) {
                    if (--cnt) {
                        pq.push(cnt);
                    }
                }
                alltime += !pq.empty() ? cycle : time;
            }
            return alltime;
        }
    };
    

    Java Version

    public class Solution {
        public int leastInterval(char[] tasks, int n) {
            Map<Character, Integer> counts = new HashMap<Character, Integer>();
            for (char t : tasks) {
                counts.put(t, counts.getOrDefault(t, 0) + 1);
            }
    
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
            pq.addAll(counts.values());
    
            int alltime = 0;
            int cycle = n + 1;
            while (!pq.isEmpty()) {
                int worktime = 0;
                List<Integer> tmp = new ArrayList<Integer>();
                for (int i = 0; i < cycle; i++) {
                    if (!pq.isEmpty()) {
                        tmp.add(pq.poll());
                        worktime++;
                    }
                }
                for (int cnt : tmp) {
                    if (--cnt > 0) {
                        pq.offer(cnt);
                    }
                }
                alltime += !pq.isEmpty() ? cycle : worktime;
            }
            
            return alltime;
        }
    }
    

  • 1
    A

    @alexander said in [C++] Clean Code:

    tasks

    Thanks for the solution. Only one minor thing, the "tasks" int variable in the while loop should be renamed as it coincides with one of the inputs.


  • 1
    M

    @alexander Thanks for your solution. Just a minor modification.. we don't really need pair<char, int>, int will be enough (for pq).


  • 0

    @phuong Thank you for point out! Updated.


  • 0

    @milu Thank you! Updated with another solution.


  • 0
    Z

    Nice and concise solution!


  • 0
    K

    Nice. One minor thing, you can save worktime with tmp.size();


  • 0
    W

    Thanks for your explanation, it is very great to see your avatar under every problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.