A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 621. Task Scheduler, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, greedy.
The notes already sitting in the source point us in the right direction:
- WA
- 51 / 69 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are leastInterval, operator.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//WA
02//51 / 69 test cases passed.
03class Solution {
04public:
05 int leastInterval(vector<char>& tasks, int n) {
06 map<char, int> counter;
07 map<char, int>::iterator it;
08
09 for(char task : tasks){
10 counter[task]++;
11 }
12
13// it = counter.begin();
14// while(!counter.empty()){
15// it->second--;
16// if(it->second == 0){
17// char key = it->first;
18// it++;
19// counter.erase(key);
20// }
21
22// }
23
24 //sort by key, descending
25 multimap<int, char, greater<int>> counterR;
26
27 for(it = counter.begin(); it != counter.end(); it++){
28 counterR.insert(make_pair(it->second, it->first));
29 }
30
31 int ans = 0;
32 //the empty spaces in between
33 int empty = 0;
34 bool first = true;
35 for(multimap<int, char>::iterator itM = counterR.begin(); itM != counterR.end(); itM++){
36 if(first){
37 ans += (itM->first-1) * (n+1) + 1;
38 empty = n * (itM->first-1);
39 first = false;
40 }else if(itM->first == counterR.begin()->first && empty != 0){
41 empty= max(empty - itM->first, 0);
42 ans++;
43 first = true;
44 }else if(empty >= itM->first){
45 empty-= itM->first;
46 }else{
47 ans += (itM->first-1) * (n+1) + 1;
48 empty = n * (itM->first-1);
49 }
50 cout << ans << " " << empty << endl;
51 }
52
53 return ans;
54 }
55};
56
57//math
58//https://leetcode.com/problems/task-scheduler/discuss/104500/Java-O(n)-time-O(1)-space-1-pass-no-sorting-solution-with-detailed-explanation
59//using map
60//Runtime: 140 ms, faster than 28.22% of C++ online submissions for Task Scheduler.
61//Memory Usage: 7.6 MB, less than 100.00% of C++ online submissions for Task Scheduler.
62//using unordered_map
63//Runtime: 92 ms, faster than 40.84% of C++ online submissions for Task Scheduler.
64//Memory Usage: 7.5 MB, less than 100.00% of C++ online submissions for Task Scheduler.
65//time: O(n), space: O(1)
66class Solution {
67public:
68 int leastInterval(vector<char>& tasks, int n) {
69 //map<int, int> counter;
70 unordered_map<int, int> counter;
71 int most = 0; //AAABBBCC, A is the task with max count, whichi is 3
72 int numMost = 0; //the number of tasks whose count is equal to max, 2 in above example
73
74 for(char task : tasks){
75 counter[task]++;
76 if(most < counter[task]){
77 most = counter[task];
78 numMost = 1;
79 }else if(most == counter[task]){
80 numMost++;
81 }
82 }
83
84 //the task with count "most" are splitted by "partCount" parts
85 int partCount = most - 1;
86 //task with count of "most" will take the empty slot
87 /*
88 when numMost is too large, "partLength" could be 0 or negative
89 in this case, we can make the interval wider than "n" and put all
90 tasks into the widened interval so that there will be no idle position
91 ("idles" will be 0)
92 */
93 int partLength = n - (numMost - 1);
94 //the empty slots formed by the task with count "most"
95 int emptySlots = partCount * partLength;
96 int availableTasks = tasks.size() - most * numMost;
97 int idles = max(0, emptySlots - availableTasks);
98
99 return tasks.size() + idles;
100 }
101};
102
103//sort by value and then by key
104class VKComparison{
105public:
106 VKComparison(){}
107 /*
108 sort by count(the larger the earlier to be popped),
109 and then by char(the smaller the earlier to be popped)
110 */
111 bool operator() (const pair<char, int>& lhs, const pair<char, int>&rhs) const{
112 return (lhs.second == rhs.second) ? (lhs.first > rhs.first) : (lhs.second < rhs.second);
113 }
114};
115
116//Priority queue, greedy
117//https://leetcode.com/problems/task-scheduler/discuss/104501/Java-PriorityQueue-solution-Similar-problem-Rearrange-string-K-distance-apart
118//Runtime: 236 ms, faster than 5.64% of C++ online submissions for Task Scheduler.
119//Memory Usage: 22.2 MB, less than 6.38% of C++ online submissions for Task Scheduler.
120class Solution {
121public:
122 int leastInterval(vector<char>& tasks, int n) {
123 unordered_map<char, int> counter;
124 priority_queue<pair<char, int>, vector<pair<char, int>>, VKComparison> pq;
125
126 for(char task : tasks){
127 counter[task]++;
128 }
129
130 for(auto it = counter.begin(); it != counter.end(); it++){
131 pq.push(make_pair(it->first, it->second));
132 }
133
134 int ans = 0;
135
136 while(!pq.empty()){
137 //current part's size
138 int part = n+1;
139
140 vector<pair<char, int>> tmpRemoved;
141
142 //while we still have space or we still have different task
143 while(part > 0 && !pq.empty()){
144 pair<char, int> cur = pq.top(); pq.pop();
145 cur.second--;
146 tmpRemoved.push_back(cur);
147 part--;
148 //we've put a task into this part
149 ans++;
150 // cout << cur.first;
151 }
152
153 for(pair<char, int> p : tmpRemoved){
154 if(p.second > 0){
155 pq.push(p);
156 }
157 }
158
159 //we've done all tasks
160 if(pq.empty()) break;
161 //if part > 0, that means there are "part" idle timeslots
162 ans += part;
163 //note that we only add these idle slots into ans if we still have some tasks to do(pq is not empty)
164 // cout << string(part, ' ');
165 }
166 // cout << endl;
167
168 return ans;
169 }
170};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.