算法题 12：任务调度算法（美团校招笔试题）

[题目]http://mp.weixin.qq.com/s/-cR07rHU91owk8nMOfhz9w

题目：任务调度在分布式调度系统中是一个很复杂很有挑战的问题。这里我们考虑一个简化的场景：假设一个中央调度机，有n个相同的任务需要调度到m台服务器上去执行。由于每台服务器的配置不一样，因此服务器执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务需要的时间为t[i]。

例如：有2个执行机a, b. 执行一个任务分别需要7min，10min，有6个任务待调度。如果平分这6个任务，即a，b各分三个任务，则最短需要30min执行完所有。如果a分这4个任务，b分2个，则最短28min执行完。

请设计调度算法，使得所有任务完成所需的时间最短

1. 简述思路

2. 请用你熟悉的编程语言编码实现以下方法，输入为m台服务器，每台机器处理一个任务的时间为t[i]，完成n个任务，输出n个任务在m台服务器的分布：

int estimate_process_time(int[] t, int m, int n);

思路：本题是个基本的题型，考虑到如何进行调度的问题，调度问题是个非常大的问题，本题简化了模型，该某型考虑的是如何组织计算单元， 使得计算的总时间最小。

其实，学习算法直到现在，我基本上完成了算法的前半部分（基础），就是如何去思考一个算法题，用什么行为去完成这个算法，我对后半部分，比如图论算法，DNF算法，数论算法等等，这些高级算法我还是没有掌握，还有就是如何进行算法分析，这个内容我也没有掌握，很遗憾，我需要学习的东西还有很多。个人感觉计算机的知识是个很庞大的体系，要想全部掌握我想很困难，所以针对个人兴趣，研究某一领域的算法是一个不错的选择，但是，基础的算法还是要会的，毕竟万变不离其宗。

此题，如果能想到使用小顶堆，基本上就算完成了算法了。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct nt{
    int n;
    int t;
    int i;
    nt (int e1, int e2) : n(0), t(e1), i(e2) {}
};

class CCompNt 
{
public:
    bool operator() (nt e1, nt e2) 
    {
        return (e2.n+1) * e2.t < (e1.n+1) * e1.t 
            || ((e2.n+1) * e2.t == (e1.n+1) * e1.t && e2.t <= e1.t);
    }
} CompNt;

class CCompNt2 
{
public:
    bool operator() (nt e1, nt e2) 
    {
        return e1.i < e2.i;
    }
} CompNt2;

void printNt(nt e)
{
    cout << "(" << e.i << "," << e.t << "," << e.n << ") ";
}

vector<nt> estimate_process_time(const vector<int> & vect, int m, int n)
{
    vector<nt> vecNt;
    for (int i=0; i<m; ++i) {
        vecNt.push_back(nt(vect[i], i));
    }

    make_heap(vecNt.begin(), vecNt.end(), CompNt);

    for (int i=0; i<n; ++i) {
        pop_heap(vecNt.begin(), vecNt.end(), CompNt);
        auto nt1 = vecNt.back();
        vecNt.pop_back();
        
        nt1.n += 1;
        vecNt.push_back(nt1);
        push_heap(vecNt.begin(), vecNt.end(), CompNt);
    }

    sort(vecNt.begin(), vecNt.end(), CompNt);

    return vecNt;
}

int main(int argc, char ** argv)
{
    int n = 6;
    int m = 2;
    vector<int> t = {
        7, 10
    };

    auto vecNt = estimate_process_time(t, m, n);

    cout << "(index, t, n)" << endl;
    for_each(vecNt.begin(), vecNt.end(), printNt);

    return 0;
}

文章的最后，还是想吐槽一下，C语言提供的数据结构真心的少，C++这方面做的不错，但是C++这方面需要不断的训练和学习，比如，这里设计小顶堆的时候，我对于比较算法的设计就出现了问题，纠结了好长时间。另外，这只是一个校招题，题目的难度你们可以从代码中感受一下，代码真的不难，难得是如何去想、去解决类似这样的问题！！！核心算法就是函数estimate_process_time中的for循环，如果你用C实现，那么heap的实现应该也算是核心代码了，这样增加了解题的难度！