1606.找到处理最多请求的服务器
1606.找到处理最多请求的服务器
题解
思路：模拟 + 有序集合 + 优先队列
这里介绍heap和redblacktree
- heap
golang中的heap是一个小根堆（可以通过插入负数来实现大根堆），通过小根堆的兴致，就可以实现优先队列queue
- redblacktree
golang的标准库是没有提供红黑树的，这里使用第三方库，并且力扣也是支持的
https://github.com/emirpasic/gods "github.com/emirpasic/gods/trees/redblacktree"
红黑树具有自平衡的特点，是一种自平衡的二叉树，所有一般用红黑树来做有序集合来使用
代码
package main import ( "container/heap" "github.com/emirpasic/gods/trees/redblacktree" ) func busiestServers(k int, arrival, load []int) (ans []int) { //实例化红黑树,available代表空闲服务器的集合 available := redblacktree.NewWithIntComparator() for i := 0; i < k; i++ { available.Put(i, nil) } //优先队列busy是正在处理请求的服务器集合 busy := hp{} //记录对应队伍去处理请求的数目 requests := make([]int, k) maxRequest := 0 for i, t := range arrival { //如果busy不为空，并且队首元素的结束时间小于等于当前请求的到达时间 for len(busy) > 0 && busy[0].end <= t { //既然成立，说明这个服务器是空闲的了，加入available available.Put(busy[0].id, nil) //移除busy队列 heap.Pop(&busy) } //如果没有一个可用，则丢弃这个请求 if available.Size() == 0 { continue } //查找大于等于i%k的第一个元素 node, _ := available.Ceiling(i % k) //如果为空，说明没有比i%k大的服务器，服务是个环，所以要从最小的开始 if node == nil { //将编号最小的服务器当作处理请求的服务器 node = available.Left() } //取出服务器id id := node.Key.(int) //对应服务器请求数目加一 requests[id]++ //处理题目要求的返回值 if requests[id] > maxRequest { maxRequest = requests[id] ans = []int{id} } else if requests[id] == maxRequest { ans = append(ans, id) } //将处理请求的服务器放入busy队列 heap.Push(&busy, pair{t + load[i], id}) //移出有序集合 available.Remove(id) } return } type pair struct{ end, id int } type hp []pair func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return h[i].end < h[j].end } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) } func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
