题目描述
容器化是当前云化趋势下的一种重要技术，容器运行需要足够的CPU资源，请实现一种CPU分配机制，满足如下设计要求：
- 假设所有虚拟机的 CPU核数都为
cpuCore。 - 为了满足可靠性要求，每个虚拟机上最多部署 2 个容器；一个容器占用一定数量的 CPU 核数，一个虚拟机上容器占用的CPU核数总和不能超过
cpuCore。
现有 A、B 两个业务，每个业务都有一个或多个微服务，每个微服务独占一个容器：
- 承载业务A 的每个容器需要的CPU核数记录于
serviceA中，serviceA.length 为容器数量，serviceA[i] 表示容器 i 所需的CPU核数。业务B 的信息serviceB含义同理。 - 业务A 需要支持反亲和策略，即业务A 的任意两个容器不能运行在同一个虚拟机上；业务B 不需要反亲和。
请计算最少需要多少个虚拟机才能满足这两个业务的资源要求？
解答要求时间限制：800ms, 内存限制：256MB
输入
首行三个整数cpuCore serviceA.length serviceB.length
第二行是 serviceA
第三行是 serviceB
2 <= cpuCore <= 1000
1 <= serviceA.length, serviceB.length <= 10^5, 1 <= serviceA[i], serviceB[i] <= cpuCore
输出
一个整数，表示最少需要多少个虚拟机
样例
输入样例 1 复制
32 3 2 16 8 16 2 7
输出样例 1
3
提示样例 1
-
每个虚拟机的CPU核数固定为 32， 业务A 的 3 个容器的CPU核数需求为 16、8、16，业务B 的 2 个容器的CPU核数需求为 2、7 。
-
由于A业务的反亲和要求，需要虚拟机的数量至少和A业务容器数相同，即 3 个；其中一种利用 3 个虚拟机满足CPU资源需求的分配方案为：
虚拟机1：(A:16，B:2)
虚拟机2：(A:8，B:7)
虚拟机3：(A:16)
注意：每个虚拟机最多部署2个容器
输入样例 2 复制
64 3 5 32 8 16 32 16 54 16 16
输出样例 2
4
提示样例 2
View Code
最少需要 4 个虚拟机。可以有多个分配方案，其中之一：
虚拟机1：(A:32，B:32)
虚拟机2：(A:8，B:54)
虚拟机3：(A:16，B:16)
虚拟机4：(B:16，B:16)
###########别人AC的############
package main import ( "container/heap" "fmt" "sort" ) type Item struct { value int priority int index int } type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority > pq[j].priority } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] old[n-1] = nil item.index = -1 *pq = old[0 : n-1] return item } func getLeastVmNum(cpuCore int, serviceA []int, serviceB []int) int { result := len(serviceA) queue := make(PriorityQueue, 0) heap.Init(&queue) for _, a := range serviceA { if a < cpuCore { heap.Push(&queue, &Item{ value: cpuCore - a, priority: cpuCore - a, }) } } sort.Slice(serviceB, func(i, j int) bool { return serviceB[i] > serviceB[j] }) for _, b := range serviceB { if queue.Len() == 0 || queue[0].priority < b { result++ heap.Push(&queue, &Item{ value: cpuCore - b, priority: cpuCore - b, }) } else { heap.Pop(&queue) } } return result } func main() { fmt.Println(getLeastVmNum(64, []int{32, 8, 16}, []int{32, 16, 54, 16, 16})) //fmt.Println(getLeastVmNum(2, []int{2}, []int{1})) //fmt.Println(getLeastVmNum(8, []int{3, 4, 5, 2, 3, 5, 2, 3, 4, 1, 8}, []int{3, 2, 1, 3, 2})) } // demo2 package main import ( "container/heap" "fmt" "sort" ) type Item struct { value int priority int index int } type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority > pq[j].priority } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] old[n-1] = nil item.index = -1 *pq = old[0 : n-1] return item } func getLeastVmNum(cpuCore int, serviceA []int, serviceB []int) int { sort.Ints(serviceA) sort.Ints(serviceB) queue := make(PriorityQueue, 0) heap.Init(&queue) result := len(serviceA) for _, a := range serviceA { if cpuCore-a > 0 { heap.Push(&queue, &Item{ value: cpuCore - a, priority: cpuCore - a, }) } } for i := len(serviceB) - 1; i >= 0; i-- { b := serviceB[i] if queue.Len() == 0 || queue[0].priority < b { result++ heap.Push(&queue, &Item{ value: cpuCore - b, priority: cpuCore - b, }) } else { heap.Pop(&queue) } } return result } func main() { fmt.Println(getLeastVmNum(64, []int{32, 8, 16}, []int{32, 16, 54, 16, 16})) //fmt.Println(getLeastVmNum(2, []int{2}, []int{1})) //fmt.Println(getLeastVmNum(8, []int{3, 4, 5, 2, 3, 5, 2, 3, 4, 1, 8}, []int{3, 2, 1, 3, 2})) }
感受：
1. 读懂题了吗?
2. 先求A的总和，因为A互斥
3. 再求空余的位置是否能容得下B么？如果容得下，就直接跳过，容不下就结果+1，并把剩余的结果重新放入队列