容器资源分配

in Algorithm Pageviews

solve actually problem!

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

  • 假设所有虚拟机的CPU核数都为coreNum
  • 基于可靠性考虑，每个虚拟机上最多部署2个容器；每个容器占用一定数量的CPU核数，一个虚拟机上容器占用的CPU核数总和不能超过coreNum

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

  • 承载业务A的每个容器需要的CPU核数记录于serviceA中，serviceA.size() 是容器数量，serviceA[i] 表示容器 i 所需的CPU核数。业务B的信息serviceB 含义相同。
  • 业务A对可靠性的要求比较高，需要支持反亲和策略，即业务A的任意两个容器不能运行在同一个虚拟机上，放置虚拟机故障导致业务受到影响而中断业务；业务B则无此要求，比较自由；

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

输入

首行三个整数coreNum，serviceA.size() serviceB.size()，第二行是serviceA，第三行serviceB

注意：

2 ≤ coreNum ≤ 1000

1 ≤ serviceA.size() ≤ 105

1 ≤ serviceB.size() ≤ 105

1 ≤ serviceA[i] ≤ coreNum

1 ≤ serviceB[i] ≤ coreNum

输出

一个整数，表示最少需要多少个虚拟机

样例1

输入

32 3 2

16 8 16

2 7

输出

3

解释

  • 每个虚拟机的核数固定是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

输入

64 3 5

32 8 16

32 16 54 16 16

输出

4

解释

最少需要4个虚拟机，其中一个分配方案为

虚拟机1:（A:32, B:32）

虚拟机2：(A:8, B:54)

虚拟机3：(A:16, B:16)

虚拟机4：(B:16, B:16)

代码实现如下:

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int GetLeastVmNum(int coreNum, const vector<int> &serviceA, const vector<int> &serviceB)
    {
        vector<int> temp(serviceB);
        sort(temp.begin(), temp.end(), greater<int>());
        multiset<int> idles;
        for (int i = 0; i < serviceA.size(); i++) {
            idles.insert(coreNum - serviceA[i]);
        }
        
        for (const auto &bCore : temp) {
            auto iter = idles.lower_bound(bCore);
            if (iter == idles.end()) {
                idles.insert(coreNum - bCore);
                continue;
            }

            idles.erase(iter++);
            idles.insert(INT_MIN);
        }
        return idles.size();
    }
};