重排使相同元素至少间隔k

func leastInterval(tasks []byte, n int) int {
	count := make([]int, 26)
	for _, v := range tasks {
		count[v-'A']++
	}
	sort.Sort(sort.Reverse(sort.IntSlice(count)))
	result := 0
	for count[0] > 0 {
		for i := 0; i <= n && count[0] > 0; i++ {
			result++
			if i < 26 && count[i] > 0 {
				count[i]--
			}
		}
		sort.Sort(sort.Reverse(sort.IntSlice(count)))
	}
	return result
}

func leastInterval(tasks []byte, n int) int {
	h := prepareHeap(tasks)
	result := 0
	set := list.New()
	for h.Len() > 0 {
		for i := 0; i <= n; i++ {
			if h.Len() == 0 && set.Len() == 0 {
				return result
			}
			result++
			if h.Len() == 0 { // 需要待命只到i==n
				continue
			}
			t := heap.Pop(h).(int)
			if t > 1 {
				set.PushBack(t - 1)
			}
		}
		for set.Len() > 0 {
			heap.Push(h, set.Remove(set.Front()).(int))
		}
	}
	return result
}

func prepareHeap(tasks []byte) *Heap {
	count := make([]int, 26)
	for _, v := range tasks {
		count[v-'A']++
	}
	h := &Heap{}
	for _, v := range count {
		if v > 0 {
			h.Push(v)
		}
	}
	heap.Init(h)
	return h
}

type Heap []int

func (h Heap) Len() int            { return len(h) }
func (h Heap) Less(i, j int) bool  { return h[i] > h[j] }
func (h Heap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *Heap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func leastInterval3(tasks []byte, n int) int {
	// 统计每个任务的数量
	count := [26]int{}
	// 数量最大的任务的数量及个数
	max, maxCount := 0, 0
	for _, v := range tasks {
		c := count[v-'A'] + 1
		count[v-'A'] = c
		if max < c {
			max = c
			maxCount = 1
		} else if max == c {
			maxCount++
		}
	}
	result := (max-1)*(n+1) + maxCount
	if result < len(tasks) {
		result = len(tasks)
	}
	return result
}

func rearrangeString(s string, k int) string {
	if k <= 1 {
		return s
	}
	result := []byte(s)
	pairs := count(result)
	cmp := func(i, j int) bool {
		if pairs[i].count == pairs[j].count {
			return pairs[i].char < pairs[j].char
		}
		return pairs[i].count > pairs[j].count
	}
	sort.Slice(pairs, cmp)
	j := 0
	for pairs[0].count > 0 {
		for i := 0; i < k; i++ {
			if pairs[0].count == 0 {
				break
			}
			if i >= len(pairs) || pairs[i].count == 0 {
				return ""
			}
			result[j] = pairs[i].char
			j++
			pairs[i].count--
		}
		sort.Slice(pairs, cmp)
	}
	return string(result)
}

type Pair struct {
	count int
	char  byte
}

func count(s []byte) []Pair {
	pairs := make([]Pair, 26)
	for _, b := range s {
		pairs[b-'a'].char = b
		pairs[b-'a'].count++
	}
	return pairs
}

func reorganizeString0(s string) string {
	return rearrangeString(s, 2)
}