ヒープで同じ作業の間を空けて全部を終える最短の時間を求める

from collections import Counter
from heapq import heapify
from heapq import heappop
from heapq import heappush


def least_time(tasks, gap):
    cnt = Counter(tasks)
    h = [-c for c in
         cnt.values()]
    heapify(h)
    time = 0
    while h:
        back = []
        done = 0
        while h and done <= gap:
            c = -heappop(h) - 1
            if c > 0:
                back.append(c)
            done += 1
        for c in back:
            heappush(h, -c)
        if h:
            done = gap + 1
        time += done
    return time

function leastTime(tasks, gap) {
  const cnt = new Map();
  for (const t of tasks) {
    const c = cnt.get(t) ?? 0;
    cnt.set(t, c + 1);
  }
  const h = [];
  for (const [, c] of cnt) {
    push(h, c);
  }
  const slot = gap + 1;
  let time = 0;
  while (h.length) {
    const back = [];
    let done = 0;
    while (h.length) {
      if (done === slot) {
        break;
      }
      const c = pop(h) - 1;
      if (c > 0) {
        back.push(c);
      }
      done++;
    }
    for (const c of back) {
      push(h, c);
    }
    if (h.length) {
      done = slot;
    }
    time += done;
  }
  return time;
}

function push(h, x) {
  h.push(x);
  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;
  }
}

function pop(h) {
  const top = h[0];
  const last = h.pop();
  if (h.length === 0) {
    return top;
  }
  h[0] = last;
  const n = h.length;
  let i = 0;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < n && h[l] > h[s]) {
      s = l;
    }
    if (r < n && h[r] > h[s]) {
      s = r;
    }
    if (s === i) {
      return top;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import "container/heap"

type maxHeap []int

func (h maxHeap) Len() int {
	return len(h)
}

func (h maxHeap) Less(
	i, j int,
) bool {
	return h[i] > h[j]
}

func (h maxHeap) Swap(
	i, j int,
) {
	h[i], h[j] = h[j], h[i]
}

func (h *maxHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *maxHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func leastTime(
	tasks []string, gap int,
) int {
	count := map[string]int{}
	for _, t := range tasks {
		count[t]++
	}
	h := &maxHeap{}
	for _, c := range count {
		heap.Push(h, c)
	}
	time := 0
	for h.Len() > 0 {
		back := []int{}
		done := 0
		for h.Len() > 0 &&
			done <= gap {
			c := heap.Pop(h).(int)
			if c > 1 {
				back = append(
					back, c-1)
			}
			done++
		}
		for _, c := range back {
			heap.Push(h, c)
		}
		if h.Len() > 0 {
			time += gap + 1
		} else {
			time += done
		}
	}
	return time
}