LeetCode/go/minimum-time-to-repair-cars.go

package main

import (
	"cmp"

	pq "github.com/emirpasic/gods/v2/queues/priorityqueue"
)

type Entry struct {
	time     int64
	rank     int64
	repaired int64
	count    int64
}

func entryCmp(a, b Entry) int {
	return cmp.Compare(a.time, b.time)
}

func repairCars(ranks []int, cars int) int64 {
	count := make(map[int64]int64)
	for _, rank := range ranks {
		rank := int64(rank)

		current, ok := count[rank]
		if !ok {
			current = 0
		}

		count[rank] = 1 + current
	}

	q := pq.NewWith(entryCmp)
	for rank, m := range count {
		q.Enqueue(Entry{
			time:     rank,
			rank:     rank,
			repaired: 1,
			count:    m,
		})
	}

	time := int64(0)
	for cars > 0 {
		next, _ := q.Dequeue()
		time = next.time

		cars -= int(next.count)
		next.repaired++
		next.time = next.rank * next.repaired * next.repaired

		q.Enqueue(next)
	}

	return time
}