理发室里有一位理发师.同时来了5位顾客,他们分别是甲、乙、丙、丁、戊,根据他们所要的发型,分别需要10分钟、12分钟、15分钟、20分钟和40分钟.怎样安排他们理发的顺序,才能使得5个人理发

Question

理发室里有一位理发师.同时来了5位顾客,他们分别是甲、乙、丙、丁、戊,根据他们所要的发型,分别需要10分钟、12分钟、15分钟、20分钟和40分钟.怎样安排他们理发的顺序,才能使得5个人理发及等候的时间最少?最少需要多少分钟?

Answer 1

一人理发时,其他人需等待,为使总的等待时间尽量短,应让理发所需时间少的人先理.甲先给需10分钟的人理发,然后15分钟的,最后24分钟的；乙先给需12分钟的人理发,然后 20分钟的.甲给需10分钟的人理发时,有2人等待,占用三人的时间和为（10×3）分；然后,甲给需 15分钟的人理发,有 1人等待,占用两人的时间和为（15×2）分；最后,甲给需 24分钟的人理发,无人等待.
　　甲理发的三个人,共用（10×3＋15×2＋24）分,乙理发的两个人,共用（12×2＋20）分.总的占用时间为
　　（10×3＋15×2＋24）＋（12×2＋20）=128（分）.
　　按照上面的安排,从第一人开始理发到五个人全部理完,用了 10＋15＋24＝49（分）.如果题目中再要求从第一人开始理发到五人全部理完的时间最短,那么做个调整,甲依次给需10,12,20分钟的人理发,乙依次给需15,24分钟的人理发,总的占用时间仍是128分钟,而五人全部理完所用时间为
　　10＋12＋20＝42（分）