1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// @Title: 找到处理最多请求的服务器 (Find Servers That Handled Most Number of Requests)
// @Author: 15816537946@163.com
// @Date: 2022-03-30 20:57:48
// @Runtime: 252 ms
// @Memory: 16.6 MB
func busiestServers(k int, arrival, load []int) (ans []int) {
    available := redblacktree.NewWithIntComparator()
    for i := 0; i < k; i++ {
        available.Put(i, nil)
    }
    busy := hp{}
    requests := make([]int, k)
    maxRequest := 0
    for i, t := range arrival {
        for len(busy) > 0 && busy[0].end <= t {
            available.Put(busy[0].id, nil)
            heap.Pop(&busy)
        }
        if available.Size() == 0 {
            continue
        }
        node, _ := available.Ceiling(i % k)
        if node == nil {
            node = available.Left()
        }
        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)
        }
        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 }