2026/06/08

[LeetCode] 621 Task Scheduler

結論題

出現最多次的task決定了「固定輪數」

用其他task去把間隔填滿

若其他task出現跟最多次task一樣多, 則一定要在「固定輪數」後再+1

若其他task出現比最多次task少, 則不影響「固定輪數」

(其他task不可能比最多次task)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
  int leastInterval(vector<char> &tasks, int n) {
    unordered_map<char, int> cnt;
    for (char task : tasks)
      cnt[task]++;
    auto maxIt =
        max_element(cnt.begin(), cnt.end(), [](const auto &p0, const auto &p1) {
          return p0.second < p1.second;
        });
    int tmp = (maxIt->second - 1) * n;
    for (auto &it : cnt)
      if (it.first != maxIt->first)
        tmp -= min(maxIt->second - 1, it.second);
    if (tmp < 0)
      return tasks.size();
    return tasks.size() + tmp;
  }
};
Labels: