算法导论之在线雇用问题

问题：假设你需要雇用一名新的办公室助理。你先前的雇用尝试都以失败告终，所以你决定找一个雇用代理。雇用代理每天给你推荐一个应聘者。你会面试这个人，然后决定要不要雇用他。你必须付给雇用代理一小笔费用来面试应聘者。要真正地雇用一个应聘者则要花更多的钱，因为你必须辞掉目前的办公室助理，还要付一大笔中介费给雇用代理。你的诺言是在任何时候，都要找到最佳人选来担任这项职务。因此，你决定在面试完每个应聘者后，如果这个应聘者比目前的办公助理更有资格，你就会辞掉目前的办公室助理，然后聘请这个新的应聘者。你愿意为这种策略而付出费用，但希望能够预测这种费用会是多少。

我们来考虑这个问题的一个变形。假设现在我们不希望面试所有的应聘者来找到最好的一个，也不希望因为不断有更好的申请者出现而不停地雇用新人解雇旧人。我们愿意雇用接近最好的应聘者，只雇用一次。我们必须遵守公司的一个要求：在每次面试后，必须或者立即提供职位给应聘者，或者告诉应聘者他们将无法得到这份工作。在最小化面试次数和最大化雇用应聘者的质量两方面如何取得平衡？

解答：

可以通过以下方式来对这个问题建模。在面试一个应聘者之后，我们能够给他一个分数；令score(i)表示给第i位应聘者的分数，并且假设没有两个应聘者的分数相同。在面试j个应聘者之后，我们知道其中哪一个分数最高，但是不知道在剩余的n-j个应聘者中会不会有更高分数的应聘者。我们决定采用这样一个策略：选择一个正整数k<n，面试前k个应聘者然后拒绝他们，再雇用其后比前面的应聘者有更高分数的第一个应聘者。如果结果是最好的应聘者在前k个面试的之中，那么我们将雇用第n个应聘者。这个策略形式化地表示在如下所示的过程ONLINEMAXIMUM(k,n)中，该过程返回的是我们希望雇用的应聘者的下标值。

/*** * @param k 前k个被拒绝的应聘者* @param n 总共n个应聘者* @return*/int ONLINEMAXIMUM(int k, int n){	int[] score = new int[n];1	int bestscore = -999999;2	for(int i = 1; i < k; i++){3		if(score[i] > bestscore){4			bestscore = score[i];		}	}5	for (int i = k+1; i < n; i++) {6		if(score[i] > bestscore){7			return i;		}	}8	return n;}

原标题：算法导论之在线雇用问题

关键词：