[题目]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执行完。
请设计调度算法，使得所有任务完成所需的时间最短
简述思路
请用你熟悉的编程语言编码实现以下方法，输入为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的实现应该也算是核心代码了，这样增加了解题的难度！
