static void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
static void siftUp(int *h, int i) {
while (i > 0 && h[(i - 1) / 2] < h[i]) {
swap(&h[(i - 1) / 2], &h[i]);
i = (i - 1) / 2;
}
}
static void siftDown(int *h, int n, int i) {
for (;;) {
int max = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && h[l] > h[max])
max = l;
if (r < n && h[r] > h[max])
max = r;
if (max == i)
return;
swap(&h[max], &h[i]);
i = max;
}
}
static void push(int *h, int *n, int val) {
h[*n] = val;
siftUp(h, (*n)++);
}
static int pop(int *h, int *n) {
int top = h[0];
h[0] = h[--*n];
siftDown(h, *n, 0);
return top;
}
int leastInterval(char *tasks, int tasksSize, int n) {
int arr[26] = {0};
for (int i = 0; i < tasksSize; i++)
arr[tasks[i] - 'A']++;
int pq[26], pqSize = 0; // max-heap of remaining counts
for (int i = 0; i < 26; i++)
if (arr[i] > 0)
push(pq, &pqSize, arr[i]);
// ring buffer of {count, nextTime}; at most 26 tasks cool down at once
int timer[26][2], head = 0, timerSize = 0;
int time = 0;
while (pqSize > 0 || timerSize > 0) {
if (timerSize > 0 && timer[head][1] <= time) {
push(pq, &pqSize, timer[head][0]);
head = (head + 1) % 26;
timerSize--;
}
if (pqSize > 0) {
int count = pop(pq, &pqSize) - 1;
if (count > 0) {
int tail = (head + timerSize++) % 26;
timer[tail][0] = count;
timer[tail][1] = time + n + 1;
}
}
time++;
}
return time;
}
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int leastInterval(vector<char> &tasks, int n) {
int time = 0;
int arr[26] = {};
queue<pair<int, int>> timer;
priority_queue<pair<int, int>> pq;
for (char ch : tasks)
arr[ch - 'A']++;
for (int i = 0; i < 26; i++) {
if (arr[i] > 0)
pq.push({arr[i], i});
}
while (!pq.empty() || !timer.empty()) {
if (!timer.empty()) {
auto [index, nextTime] = timer.front();
if (nextTime <= time) {
pq.push({arr[index], index});
timer.pop();
}
}
if (!pq.empty()) {
auto [count, index] = pq.top();
pq.pop();
arr[index]--;
if (arr[index] > 0)
timer.push({index, time + n + 1});
}
time++;
}
return time;
}
};
package heaps
import (
"container/heap"
"sort"
)
type maxHeap struct{ sort.IntSlice }
func (h maxHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *maxHeap) Push(x any) { h.IntSlice = append(h.IntSlice, x.(int)) }
func (h *maxHeap) Pop() any {
old := h.IntSlice
x := old[len(old)-1]
h.IntSlice = old[:len(old)-1]
return x
}
type cooldown struct{ count, nextTime int }
func leastInterval(tasks []byte, n int) int {
var arr [26]int
for _, ch := range tasks {
arr[ch-'A']++
}
pq := &maxHeap{} // remaining counts
for _, c := range arr {
if c > 0 {
pq.IntSlice = append(pq.IntSlice, c)
}
}
heap.Init(pq)
var timer []cooldown
time := 0
for pq.Len() > 0 || len(timer) > 0 {
if len(timer) > 0 && timer[0].nextTime <= time {
heap.Push(pq, timer[0].count)
timer = timer[1:]
}
if pq.Len() > 0 {
if count := heap.Pop(pq).(int) - 1; count > 0 {
timer = append(timer, cooldown{count, time + n + 1})
}
}
time++
}
return time
}
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] arr = new int[26];
for (char ch : tasks)
arr[ch - 'A']++;
// remaining counts
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int c : arr)
if (c > 0)
pq.offer(c);
Queue<int[]> timer = new ArrayDeque<>(); // {count, nextTime}
int time = 0;
while (!pq.isEmpty() || !timer.isEmpty()) {
if (!timer.isEmpty() && timer.peek()[1] <= time)
pq.offer(timer.poll()[0]);
if (!pq.isEmpty()) {
int count = pq.poll() - 1;
if (count > 0)
timer.offer(new int[] {count, time + n + 1});
}
time++;
}
return time;
}
}
class MaxHeap {
constructor() {
this.data = [];
}
size() {
return this.data.length;
}
top() {
return this.data[0];
}
push(val) {
const h = this.data;
h.push(val);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p] >= h[i]) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
pop() {
const h = this.data;
const top = h[0];
const last = h.pop();
if (h.length === 0) return top;
h[0] = last;
let i = 0;
for (;;) {
let max = i;
const l = 2 * i + 1,
r = 2 * i + 2;
if (l < h.length && h[l] > h[max]) max = l;
if (r < h.length && h[r] > h[max]) max = r;
if (max === i) return top;
[h[max], h[i]] = [h[i], h[max]];
i = max;
}
}
}
/**
* @param {character[]} tasks
* @param {number} n
* @return {number}
*/
var leastInterval = function (tasks, n) {
const arr = new Array(26).fill(0);
for (const ch of tasks) arr[ch.charCodeAt(0) - 65]++;
const pq = new MaxHeap(); // remaining counts
for (const c of arr) if (c > 0) pq.push(c);
const timer = []; // [count, nextTime]
let head = 0;
let time = 0;
while (pq.size() > 0 || head < timer.length) {
if (head < timer.length && timer[head][1] <= time) pq.push(timer[head++][0]);
if (pq.size() > 0) {
const count = pq.pop() - 1;
if (count > 0) timer.push([count, time + n + 1]);
}
time++;
}
return time;
};
import heapq
from collections import Counter, deque
from typing import List
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
pq = [-c for c in Counter(tasks).values()] # negate for a max-heap
heapq.heapify(pq)
timer = deque() # (count, next_time)
time = 0
while pq or timer:
if timer and timer[0][1] <= time:
heapq.heappush(pq, -timer.popleft()[0])
if pq:
count = -heapq.heappop(pq) - 1
if count > 0:
timer.append((count, time + n + 1))
time += 1
return time
use std::collections::{BinaryHeap, VecDeque};
impl Solution {
pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
let mut arr = [0; 26];
for ch in tasks {
arr[(ch as u8 - b'A') as usize] += 1;
}
// remaining counts
let mut pq: BinaryHeap<i32> = arr.into_iter().filter(|&c| c > 0).collect();
let mut timer = VecDeque::new(); // (count, next_time)
let mut time = 0;
while !pq.is_empty() || !timer.is_empty() {
if let Some(&(count, next_time)) = timer.front() {
if next_time <= time {
pq.push(count);
timer.pop_front();
}
}
if let Some(count) = pq.pop() {
if count > 1 {
timer.push_back((count - 1, time + n + 1));
}
}
time += 1;
}
time
}
}