一天一题，深搜枚举与区间合并(0809)

这是前不久一个朋友面试国外云服务跟电商网站某迅的题目。这个题目很有意思，我们来看一下。

题目：

云 服务现在特别的流行，现在公司的一台主机上，有n个虚拟的主机，每台开启的虚拟主机都有需要一定的带宽（不开的虚拟主机带宽为0个单位），经过评估，第i 个最少需要lower[i]单位，最高需要upper[i]单位的带宽。现在想知道，这n台机器，需要带宽的总和有多少种不同可能？

为了简化问题，我们假定n <= 15, 0 <= lower[i] <= upper[i] <= 10 ^ 6.

给一个例子：

n = 2

lower[] = {1, 10}

upper[] = { 2, 15}

如果都关闭，结果为1种可能，0

如果只有第0台开启，那么结果有2种可能，1,2

如果只有第1台开启，那么结果有6种可能， 10， 11， 。。，15

如果1,2同时开启，那么结果为有7种可能 , 11, 12, ..17

排除重复的，最后的结果为11种。

思考

这 个题目一上手估计很多人都束手无策（包括那个面试的朋友），这个题目很像一个背包问题，我们尝试着用动态规划的方法来解决。我们注意到，区间的上限是 15*10^6≈10^7，对于每一台机器，如果我们都来枚举占用带宽多少的话，极端情况下需要10^6,总复杂度为10^7*10^6等于10^13次 方。按照一台机器 10^9的速度，需要1万秒才能算出极端的结果！这条路行不通。

我们换一种思路来思考这个问题，假如我们知道哪些机器已 经开启了。那么我们能否知道这个结果的区间呢？答案当然可以，需要的带宽区间为[sum{lower[i]}, sum{upper[i]}]。这是一个闭区间。那么我们进一步来想，我们虽然不能确定哪些机器已经开启，但我们可以枚举出所有的可能(2^15)。也就 是最后我们可能得到2^15个闭区间，然后做区间的合并。

这里我们稍微简单介绍一下区间合并统计大小，区间合并可以用贪心算法来解决。我们将所有的区间按照l升序进行排序，然后用一个right，表示已经统计的最右端在哪边。

• 如果l[i] > right， 那么说明两个区间中间有一些空隙，我们将right 变成 right = l[i] - 1;

• 如果r[i] > right， 那么新增的个数为 r[i] - right， 然后 right = r[i]

• 如果r[i] <= right, 不用操作。

至此，我们已经解决了问题了，这个问题分为两部分：

• 枚举机器状态

• 区间合并

可以简单看下后面我写的代码（头条排版不好）：

枚举状态:

    private void dfs(int dep, int[] lowerBound, int[] upperBound, int low, int upp){

    if (dep == n){

    Segment segment = new Segment(low, upp + low);

    sList.add(segment);

    return;

    }

    dfs(dep + 1, lowerBound, upperBound, low, upp);

    dfs(dep + 1, lowerBound, upperBound, low + lowerBound[dep], upp + upperBound[dep] - lowerBound[dep]);

    }

区间统计：

    public int getAns(List<Segment> list){

    int ret = 1;

    int r = 0;

    for (Segment each : list){

    if (each.begin > r){

    r = each.begin - 1;

    }

    if (each.end > r){

    ret += (each.end - r);

    r = each.end;

    }

    }

    return ret;

    }

大家可以关注我的头条号，基本上每天一道大公司的面试算法题。