621. Task Scheduler With Gaps

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

https://leetcode.com/problems/rearrange-string-k-distance-apart/

与一般的Scheduling问题不同，这题要求每个task之间最少间隔x gaps.

做法是priority_queue + greedy (未证明)，以”AAABBC”，x=3为例，greedy的过程大致为，从frequency最高的元素开始，依次填空

  1. A__A__A__
  2. AB_AB_A__
  3. ABCAB_A__ (注意trailing idle time是不需要的)

所以最终的结果是ABCAB_A= 7

Implementation 复杂度为 O(nlogn) 应为每个元素都会被插入pq一次，这题有O(n)的解法-time-O(1)-space-1-pass-no-sorting-solution-with-detailed-explanation)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> taskCounts;
        priority_queue<int> taskQ;

          // O(t) count
        for (auto t : tasks) {
            ++taskCounts[t];
        }

          // O(tlogt) insert
        for (auto [t, freq]: taskCounts) {
            taskQ.push(freq);
        }

        int cycle = 0;
        while (!taskQ.empty()) {
            vector<int> remainingTasks;

            int idle = 0;
            int gaps = n;
              // note while (--i) and while (i--) executes different times
              // * while (--i) i-1 times
              // * while (i--) i   times
            while (gaps-- >= 0) {
                if (!taskQ.empty()) {
                    remainingTasks.push_back(taskQ.top());
                    taskQ.pop();
                    ++cycle;
                } else {
                    ++idle;
                }
            }

            for (auto tf : remainingTasks) {
                if (--tf > 0) {
                    taskQ.push(tf);
                }
            }

            if (!taskQ.empty()) {
                // to avoid trailing idle time
                cycle += idle;
            }
        }

        return cycle;
    }
};