某银行有4个柜台，假设某天有若干为客户来办理业务，每个客户到达银行的时间和取款需要的时间分布分别用两个数组arrive_time（已经按到达时间排序）和process_time来描述。
请写程序计算所有客户的平均等待时间，假设每个客户取取款之前先拿到号排对，然后在任意一个柜台有空闲的时候，号码数最小的客户上去办理，假设所有的客户拿到号码之后不会失去耐心走掉。
测试用例：
NSArray<NSNumber *> *arrive_time = @[@1.0, @2.0, @3.0, @4.0, @4.0, @8.0];
NSArray<NSNumber *> *process_time = @[@50.0, @20.0, @11.0, @25.0, @30.0, @40.0];
// 计算过程：24.0 / 6 所有用户需要等待的总时间/用户总数
输出结果：4.0
分析：首先不要被银行取款这个场景迷惑，这个算法跟实际生活中场景有很大的不同，首先，arrive_time是已经确定的,另外所有人占用仅有的4个柜台时间也是已经确定好的，不会有增加和减少的行为。
那么实际这个算法就是：按照arrive_time的序号依次开始,当一个顾客到达后，就需要判断是否有空闲的柜台，这里就需要一个数组来存放已经使用的柜台，数组的数组就用来存放当前剩余多久能够完成正在进行的客户取款。
NSMutableArray<NSNumber *> *servers = [NSMutableArray array];
然后还需要一个变量存储所有顾客需要等待的累加的时间：
CGFloat allWaitTime = 0;
那么算法的最基本结构就出来了：
// 顾客到达时间数组
NSArray<NSNumber *> *arrive_time = @[@1.0, @2.0, @3.0, @4.0, @4.0, @8.0];
// 对应到达时间每一个顾客需要占用柜台的时间数组
NSArray<NSNumber *> *process_time = @[@50.0, @20.0, @11.0, @25.0, @30.0, @40.0];
// 被占用的柜台数组
NSMutableArray<NSNumber *> *servers = [NSMutableArray array];
// 客户需要等待的总时间
CGFloat allWaitTime = 0;
// 遍历每一个顾客，计算需要等待的总时间
for (int i = 0; i < arrive_time.count; i++) {
}
每当一个顾客进来我们就需要先判断是否有正在服务的柜台，如果servers的数量小于4，那么就可以直接进行服务，不需要等到，而这个柜台需要被占用的时间刚好就是这个顾客对应的process_time中的时间，所以直接在servers添加一个元素，值为process_time对队应index的值，用于记录一个柜台被占用，并且需要剩余多少时间才会空闲。
for (int i = 0; i < arrive_time.count; i++) {
// 当前存在空闲的柜台，顾客直接进行取款
if (servers.count < 4) {
// 这个柜台被占用，并且需要这个顾客需要的取款时间后才会空闲
[servers addObject:process_time[i]];
NSLog(@"第 %d 个 顾客不需要等待直接服务", i + 1);
} else { // 没有空闲的柜台，计算需要等待多久
}
}
如果没有空闲的柜台我们，我们就需要计算需要等待时间最短柜台还需要多少时间空闲。既然需要计算时间，我们首先需要一个时间线，来记算时间的流逝，不然的话是无法计算剩余等待时间等这些的。那么如何计算呢，这里其实已经有了，就是每一个顾客的到达时间，第一个顾客到达时间为 1，第二个为 2，以第一个顾客到达时间为起始时间，那么第二个顾客达到是，时间增加了 1 个单位，当第 3 个顾客到达时，时间又过去了 1 个单位。
每当一个顾客来的时候，如果存在正在占用的柜台，我们就需要将所有被占用柜台的剩余服务时间进行处理，减去这个顾客到达时和上一个顾客达到的时间差，这样所有的服务中柜台的剩余等待时间就会成功的更新，并且如果剩余等待时间小于等于这名顾客和上一名顾客到达时间的差值，就证明这个柜台已经完成服务，还需要将它从servers数组中移除：
for (int i = 0; i < arrive_time.count; i++) {
// 保存剩余时间最小的柜台的时间
CGFloat minLast = MAXFLOAT;
// 保存剩余时间最小的柜台的index
NSInteger minIndex = 0;
// 当存在服务中柜台是，需要对柜台剩余时间进行刷新
if (servers.count > 0) {
// 保存已经服务完成的柜台，用于后面将他们从servers中移除
NSMutableArray *removeArray = [NSMutableArray array];
// 遍历所有服务中的柜台，即servers中的每一个元素
for (int j = 0; j < servers.count; j++) {
// 上一个顾客到达的时间
NSInteger preArriveTime = i > 0 ? arrive_time[i - 1].floatValue : 0;
// 当前顾客到达的时间就是他距离上一个顾客到达时间的差值
// 这个差值就是时间线的标准
CGFloat pastTime = arrive_time[i].floatValue - preArriveTime;
// 当前柜台剩余的时间就是上一个顾客来的时候，剩余的服务时间减去当前顾客距离上一个到达时间的差值
CGFloat lastTime = servers[j].floatValue - pastTime;
// 更新当前柜台的剩余等待时间
servers[j] = [NSNumber numberWithFloat:lastTime];
// 计算剩余等待时间最小的柜台
if (lastTime < minLast) {
minLast = lastTime;
minIndex = j;
}
// 如果剩余时间小于0，它在之后会被从servers中移除
if (lastTime < 0) [removeArray addObject:servers[j]];
}
// 将已经空闲的柜台从servers中移除
[servers removeObjectsInArray:removeArray];
}
// 当前存在空闲的柜台，顾客直接进行取款
if (servers.count < 4) {
// 这个柜台被占用，并且需要这个顾客需要的取款时间后才会空闲
[servers addObject:process_time[i]];
NSLog(@"第 %d 个 顾客不需要等待直接服务", i + 1);
} else { // 没有空闲的柜台，计算需要等待多久
}
}
更新完所有服务中柜台的剩余时间后，再去计算如果柜台都在等待中，那么顾客需要等待的时间：
NSLog(@"第 %d 个 顾客需要等待 %f s", i + 1, servers[minIndex].floatValue);
allWaitTime += servers[minIndex].floatValue;
servers[minIndex] = [NSNumber numberWithFloat:(servers[minIndex].floatValue + process_time[i].floatValue)];
完整算法代码：
void checkTime(NSArray<NSNumber *> *arrive_time, NSArray<NSNumber *> *process_time) {
// 被占用的柜台数组
NSMutableArray<NSNumber *> *servers = [NSMutableArray array];
// 客户需要等待的总时间
CGFloat allWaitTime = 0;
// 遍历每一个顾客，计算需要等待的总时间
for (int i = 0; i < arrive_time.count; i++) {
// 保存剩余时间最小的柜台的时间
CGFloat minLast = MAXFLOAT;
// 保存剩余时间最小的柜台的index
NSInteger minIndex = 0;
// 当存在服务中柜台是，需要对柜台剩余时间进行刷新
if (servers.count > 0) {
// 保存已经服务完成的柜台，用于后面将他们从servers中移除
NSMutableArray *removeArray = [NSMutableArray array];
// 遍历所有服务中的柜台，即servers中的每一个元素
for (int j = 0; j < servers.count; j++) {
// 上一个顾客到达的时间
NSInteger preArriveTime = i > 0 ? arrive_time[i - 1].floatValue : 0;
// 当前顾客到达的时间就是他距离上一个顾客到达时间的差值
// 这个差值就是时间线的标准
CGFloat pastTime = arrive_time[i].floatValue - preArriveTime;
// 当前柜台剩余的时间就是上一个顾客来的时候，剩余的服务时间减去当前顾客距离上一个到达时间的差值
CGFloat lastTime = servers[j].floatValue - pastTime;
// 更新当前柜台的剩余等待时间
servers[j] = [NSNumber numberWithFloat:lastTime];
// 计算剩余等待时间最小的柜台
if (lastTime < minLast) {
minLast = lastTime;
minIndex = j;
}
// 如果剩余时间小于0，它在之后会被从servers中移除
if (lastTime < 0) [removeArray addObject:servers[j]];
}
// 将已经空闲的柜台从servers中移除
[servers removeObjectsInArray:removeArray];
}
// 当前存在空闲的柜台，顾客直接进行取款
if (servers.count < 4) {
// 这个柜台被占用，并且需要这个顾客需要的取款时间后才会空闲
[servers addObject:process_time[i]];
// NSLog(@"第 %d 个 顾客不需要等待直接服务", i + 1);
} else { // 没有空闲的柜台，计算需要等待多久
// NSLog(@"第 %d 个 顾客需要等待 %f s", i + 1, servers[minIndex].floatValue);
allWaitTime += servers[minIndex].floatValue;
servers[minIndex] = [NSNumber numberWithFloat:(servers[minIndex].floatValue + process_time[i].floatValue)];
}
}
CGFloat res = allWaitTime / arrive_time.count;
NSLog(@"计算完成 \n总等待时间 %.1f \n顾客数%zd \n平均等待时间: %.1f\n", allWaitTime, arrive_time.count, res);
}
打印测试输出：
NSArray<NSNumber *> *arrive_time = @[@1.0, @2.0, @3.0, @4.0, @4.0, @8.0];
NSArray<NSNumber *> *process_time = @[@50.0, @20.0, @11.0, @25.0, @30.0, @40.0];
checkTime(arrive_time, process_time);
总等待时间 24.0
顾客数6
平均等待时间: 4.0
耗时: 0.284076 ms
复杂度分析：
最外层需要遍历所有顾客为n，内部更新servers需要最多4次，移除servers最多4次，假定动态数组增加和删除都是O(1)，那么总共需要n * (4 + 4)，复杂度为O(n)。
测试1000条数据需要的运行时间：
NSMutableArray<NSNumber *> *arrive_time = [NSMutableArray array];
for (int i = 0; i < 10000; i++) {
[arrive_time addObject:[NSNumber numberWithFloat:i]];
}
NSMutableArray<NSNumber *> *process_time = [NSMutableArray array];
for (int i = 0; i < 10000; i++) {
[process_time addObject:[NSNumber numberWithFloat:i % 10 + 10]];
}
CFAbsoluteTime startTime =CFAbsoluteTimeGetCurrent();
checkTime(arrive_time, process_time);
CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
NSLog(@"\n耗时: %f ms", linkTime *1000.0);
总等待时间 131176253.0
顾客数10000
平均等待时间: 13117.6
耗时: 6.420970 ms
总结
这个题主要是考察思维的，能不能从看似没有头绪的问题中，找到如何选择时间的参照系这个关键，至于之后的时间的计算就是很简单的了。
网友评论