这是一道很有难度的题,代码我也用的官方解,我把每一行的详细解释都写在注释里,看的会比较清楚一些。大致说明一下这道题,这个场景很像一致hash负载均衡的实现,所以我想的也是用一个hash来存一个大结构,包含该服务器的请求数、正在运行请求的结束时间等,随着时间遍历进行减操作,但是这样太过复杂且时间过长。官方解代码的思考很好,跟着时间过程来模拟,用优先队列来维护繁忙的服务器,然后做判断,看哪个服务器可用于下一个请求,而可用服务器有两种方法构造,再用一个队列或者是有序集合,go语言有支持的GODS(一个数据结构库),用红黑树来做更加简洁。
func busiestServers(k int, arrival, load []int) (ans []int) {
// 定义有序集合(红黑树结构),键类型为int
available := redblacktree.NewWithIntComparator()
// 将空闲的服务器存放集合中,available就是存放可用服务器的
for i := 0; i < k; i++ {
available.Put(i, nil)
}
// busy:堆(优先队列)中存放的是繁忙的服务器,以服务器中请求结束的时间排序,做一个小顶堆
busy := hp{}
// requests:用来存放每台服务器处理的请求次数
requests := make([]int, k)
maxRequest := 0
for i, t := range arrival { // 顺序遍历,因为arrival中请求的到达时间是按照顺序的,优先处理先到达的
// 遍历每次请求到达,如果繁忙服务器中的结束时间小于该请求的到达时间,那么该服务器在完成正在运行的请求就可以运行t时刻来的请求。
for len(busy) > 0 && busy[0].end <= t {
available.Put(busy[0].id, nil) // 作为空闲服务器放入集合
heap.Pop(&busy) // 出栈
}
// 如果集合中大小为0,说明t时刻没有空闲的服务器,直接舍弃
if available.Size() == 0 {
continue
}
// 根据题意,优先判断大于等于(i % k)个服务器,如果此服务器繁忙,返回key最小的
// Ceiling(天花板)的方法解释是这样的:
// Ceiling finds ceiling node of the input key, return the ceiling node or nil if no ceiling is found. Second return parameter is true if ceiling was found, otherwise false.
// Ceiling node is defined as the smallest node that is larger than or equal to the given node. A ceiling node may not be found, either because the tree is empty, or because all nodes in the tree are smaller than the given node.
// Key should adhere to the comparator's type assertion, otherwise method panics.
// Ceiling会去找比key大的节点,如果找不到就返回false。
node, _ := available.Ceiling(i % k)
if node == nil {
node = available.Left()
}
// 取出选择服务器的id
id := node.Key.(int)
// 该服务器处理请求+1
requests[id]++
// 逻辑判断
if requests[id] > maxRequest {
maxRequest = requests[id]
ans = []int{id}
} else if requests[id] == maxRequest {
ans = append(ans, id)
}
// 将该服务器再次入堆中,集合中再删除该服务器,意思也就是该服务器再次变成繁忙状态,不可用。
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 }
func busiestServers(k int, arrival, load []int) (ans []int) {
// 建立一个队列作为可用服务器的集合
available := hi{make([]int, k)}
for i := 0; i < k; i++ {
available.IntSlice[i] = i
}
// 这些定义和上面的有序集合代码都一样
busy := hp{}
requests := make([]int, k)
maxRequest := 0
for i, t := range arrival {
for len(busy) > 0 && busy[0].end <= t {
// 存进可用服务器队列中的newi,这个地方的处理目的其实是,假设现在某一个请求i过来了,繁忙服务器队列中存放的服务器id可用,我们要保证该服务器id入队列可用服务器时,其值不能小于i,因为后续的处理有(i%k)的计算
// 更进一步解释,假设有三个服务器,四个请求
// 当三个服务器处理完了,第四个请求来了
// 此时队列中的busy[0]的id应该是0,我们直接heap.Push(&available,busy[0].id)会把0放进去,同理如果后面1、2也满足条件都会入队列,
// 那么下面出队列的操作,即heap.Pop(&available).(int) % k,就会用0服务器来计算了,而我们要的是4%3=1服务器,所以这个地方要入队列的其实是1。
heap.Push(&available, i+((busy[0].id-i)%k+k)%k) // 保证得到的是一个不小于 i 的且与 id 同余的数
heap.Pop(&busy)
}
// 下面的思路都一样
if available.Len() == 0 {
continue
}
id := heap.Pop(&available).(int) % k
requests[id]++
if requests[id] > maxRequest {
maxRequest = requests[id]
ans = []int{id}
} else if requests[id] == maxRequest {
ans = append(ans, id)
}
heap.Push(&busy, pair{t + load[i], id})
}
return
}
type hi struct{ sort.IntSlice }
func (h *hi) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hi) Pop() interface{} {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
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 }