首页 > 代码库 > 电梯调度
电梯调度
电梯在我们的生活中很常见,但是电梯中的算法我们还是不太了解。
现在我们来更仔细的分析一下这个问题,看看怎么样优化一下。假设电梯停在第 i 层楼,我们计算出所有乘客总共爬楼梯的层数是Y。如果有N1个乘客想去的楼层在第 i 层之下,有N2个乘客正好想去的楼层是第 i 层,有N3个乘客想去的楼层在第 i 层之上。这个时候,重点来了:如果电梯改停在i-1层,所有目的地在第i - 1层以下的乘客可以少爬1层,总共少爬N1层,所有在i层及以上的乘客要多爬一层,总共多爬N2+N3层,这时总共需要爬Y-N1+N2+N3。
反之,如果电梯在i+1层停所有目的地在第 i 层以上的乘客可以少爬1层,总共少爬N3层,所有在 i 层及以下的乘客要多爬一层,总共多爬N1+N2层,这时总共需要爬
Y+N1+N2-N3层。
可见,当N1 > N2+N3 时,电梯在第i-1层楼停更好;当N1+N2 < N3 时,电梯在i+1层停更好。其他情况在第i层更好。
如此一来,问题的解法就出来了,从第一层开始考察,计算各位乘客走的楼层的数目,然后根据N1,N2,N3之间的关系进行调整,知道找到最佳楼层,这样算法时间复杂度优化到了O(N)。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。