Sponsored
Sponsored
The key idea is to figure out the task with the maximum frequency and set its intervals accordingly.
Assume the task with the highest frequency appears max_count times. Arrange tasks such that the remaining tasks are fitted in between the most frequent task considering the cooldown period.
The formula for the minimum intervals required is determined by the max frequency task with necessary slots due to the cooling period. The result is the maximum of the total tasks or the formed slots, i.e., max(len(tasks), (max_count - 1) * (n + 1) + count_max), where count_max is the number of tasks with frequency equal to max_count.
Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the space for the frequency array is constant.
1using System;
2using System.Linq;
3
4class Solution {
5 public int LeastInterval(char[] tasks, int n) {
6 int[] map = new int[26];
7 foreach (char c in tasks) {
8 map[c - 'A']++;
9 }
10 Array.Sort(map);
11 int max_val = map[25] - 1;
12 int idle_slots = max_val * n;
13
14 for (int i = 24; i >= 0 && map[i] > 0; i--) {
15 idle_slots -= Math.Min(map[i], max_val);
16 }
17 return idle_slots > 0 ? idle_slots + tasks.Length : tasks.Length;
18 }
19
20 static void Main() {
21 char[] tasks = {'A','A','A','B','B','B'};
22 int n = 2;
23 Solution sol = new Solution();
24 Console.WriteLine(sol.LeastInterval(tasks, n)); // Output: 8
25 }
26}This C# solution functions by using an integer array to compute task frequencies, sorts them, and calculates idle slots needed around the most frequent task. Finally, it returns the sum of idle slots and task length if idle slots are positive; otherwise, it returns the length of tasks.
Another way is to simulate the task processing using a priority queue to always pick the task with the highest remaining count that can be scheduled. A min-heap or a max-heap is useful to efficiently get the next task. As tasks are being processed, they are placed on cooldown before they can be executed again, managed by a cooldown queue.
Time Complexity: O(N log N), where N is determined by sorting. Space Complexity: O(1).
1using System.Collections.Generic;
using System.Linq;
class Solution {
public int LeastInterval(char[] tasks, int n) {
Dictionary<char, int> dict = new Dictionary<char, int>();
foreach (char task in tasks) {
if (dict.ContainsKey(task))
dict[task]++;
else
dict[task] = 1;
}
PriorityQueue<int, int> pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
foreach (var kvp in dict) {
pq.Enqueue(kvp.Value, kvp.Value);
}
int time = 0;
while (pq.Count > 0) {
List<int> temp = new List<int>();
for (int i = 0; i <= n; ++i) {
if (pq.Count > 0) temp.Add(pq.Dequeue());
time++;
if (pq.Count == 0 && temp.Count == 0) break;
}
foreach (int count in temp) {
if (--count > 0) pq.Enqueue(count, count);
}
}
return time;
}
static void Main() {
char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
int n = 2;
Solution sol = new Solution();
Console.WriteLine(sol.LeastInterval(tasks, n)); // Output: 8
}
}This C# solution executes the scheduling by utilizing a priority queue to efficiently manage the tasks based on their cooldown effects.