/** * o(n)的解决方法,经测试和标准答案的结果是一样的 * 模拟银行业务场景: * 用一个优先队列保存四个元素,四个元素为正在进行的任务执行完成的时间 * (优先队列会按照任务结束的时间排序, 从队列取到的第一个任务总是最先完成的那个) * 用一个变量保存总的等待时间 * * 先往优先队列放入4个任务,这4个任务的等待时间为0,所以优先队列的4个值为4个任务对应的到达时间和执行时间之和, * 再把剩下的任务一个个加入优先队列,对于这个要加入的任务,他的等待时间为优先队列的第一个元素(四个任务中最先完成的任务) * 的值减去当前任务的开始时间,所以这个要加入的任务的完成时间为“他的等待时间 + 任务到达时间 + 任务执行时间” * 依次遍历完所有的任务,得到最终等待时间 * @param arrive_time * @param process_time * @return */ private static double solution(int[] arrive_time, int[] process_time) { PriorityQueue<Integer> processing = new PriorityQueue<>(); for (int i = 0; i < 4; i++) { processing.add(arrive_time[i] + process_time[i]); } int totalWaitTime = 0; int waitTime; for (int i = 4; i < arrive_time.length; i++) { waitTime = processing.peek() - arrive_time[i]; //waitTime为负数时不需要等待 waitTime = Math.max(waitTime, 0); totalWaitTime += waitTime; processing.poll(); processing.add(arrive_time[i] + process_time[i] + waitTime); } return totalWaitTime * 1.0 / arrive_time.length; }
t =arrive_time[0]user_num =200p =0window_num =4windows =[(-1, 0)]*window_num # user_id, finish_time, -1 stands for nobody herewait_q =[]wait_time_sum =0.0whilep<user_num: #60*60*24 times at mostwhilet==arrive_time[p]:wait_q.append(p)p +=1fori inrange(window_num):user_id, finish_time =windows[i]iffinish_time==t:wait_time_sum +=t-process_time[user_id]-arrive_time[user_id]windows[i] =(-1, 0)ifwindows[i][0]==-1:next_user =wait_q.pop(0)windows[i] =(next_user, t+process_time[next_user])t +=1printwait_time_sum/len(arrive_time)
OC代码解题
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *arrive_time = @[@1,@2,@3,@4,@4,@8];
NSArray *process_time = @[@50,@20,@11,@25,@30,@40];
if (arrive_time.count < 4) {
NSLog(@"等待时间为:%d",0);
return;
}
NSMutableArray *array = [NSMutableArray array];
for (int i = 0; i < 4; i++) {
NSInteger total = [arrive_time[i] integerValue] + [process_time[i] integerValue];
[array addObject:[NSNumber numberWithInteger:total]];
}
NSInteger totalWaiteTime = 0;
NSInteger waiteTime = 0;
for (int i = 4; i < arrive_time.count; i++) {
NSInteger min = [self fetchMinArray:array];
NSInteger processTime = [array[min] integerValue];
waiteTime = processTime - [arrive_time[i] integerValue];
waiteTime = waiteTime <= 0 ? 0 : waiteTime;
totalWaiteTime +=waiteTime;
array[min] = [NSNumber numberWithInteger:[array[min] integerValue] + [process_time[i] integerValue]];
waiteTime = 0;
}
NSLog(@"等待时间为:%lu",totalWaiteTime/arrive_time.count);
}
- (NSInteger)fetchMinArray:(NSArray *)minArray {
NSInteger min = 0;
for (NSInteger i = 1; i < minArray.count; i++) {
if ([minArray[min] integerValue] > [minArray[i] integerValue]) {
min = i;
}
}
return min;
}
arrive_time.push_back(1);