容器资源分配

题目描述

容器化是当前云化趋势下的一种重要技术，容器运行需要足够的CPU资源，请实现一种CPU分配机制，满足如下设计要求：

• 假设所有虚拟机的 CPU核数都为 cpuCore 。
• 为了满足可靠性要求，每个虚拟机上最多部署 2 个容器；一个容器占用一定数量的 CPU 核数，一个虚拟机上容器占用的CPU核数总和不能超过 cpuCore 。

现有 A、B 两个业务，每个业务都有一个或多个微服务，每个微服务独占一个容器：

• 承载业务A 的每个容器需要的CPU核数记录于 serviceA 中，serviceA.length 为容器数量，serviceA[i] 表示容器 i 所需的CPU核数。业务B 的信息 serviceB 含义同理。
• 业务A 需要支持反亲和策略，即业务A 的任意两个容器不能运行在同一个虚拟机上；业务B 不需要反亲和。

请计算最少需要多少个虚拟机才能满足这两个业务的资源要求？

首行三个整数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

• 每个虚拟机的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

最少需要 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，并把剩余的结果重新放入队列