经典百度面试算法:万人工厂分配任务

: A厂有1万个工人,编号0-9999,( EE[10000] ), 1个厂长( GG )分派任务, 1个监工( MM )管理工人.厂子忙的时间不确定,可能突然很忙,1天接到任务5000多个,1个任务只能分配给1个工人做, 也可能好几十天没新任务.厂长分配任务给这1万个工人干,按工人编号一个一个来,到最后一个工人就又从头开始,任务完成时间各不相同,可能一个工人在分配任务的时候手里还有任务, 就得换下一个。

  但是这1万个工人都很懒,领到了任务先不做,需要监工1个1个去问,如果工人有任务,就做,如果工人没任务,则不做。厂长只管分任务,1个1个来,可能几天也没新任务,不累;但是监工很累,监工每天都要看所有工人的情况,即使这些工人都没有任务, 实际上每天工人(80%左右)是没任务的,请问,怎么让监工的工作轻松下来. 比如说每天只问1小半工人.

  Peak Wong:

  分析如下:

  因为“任务完成时间各不相同” ,所以有可能a,b,c某天都有任务,但b的任务最先完成,那么当b的任务完成后,有任务的人的工号可能是不连续的;

  用一个数组表示1万个工人是否有任务,并保存最后被分配任务的人的工号;

  1)从前一天“最后被分配任务的人的工号”开始,依次问下一个工号的人,置对应的工作状态,直到碰到前一天无工作,且当天也无工作的人;并更新当步最后有工作的人的工号为当天的“最后被分配任务的人的工号”;

  2)从前一天“最后被分配任务的人的工号”开始,依次问上一个工号且前一天有工作的人;

  问题是监工可以知道那些信息,否则还不是一个一个接着去问。

  还有就是tailzhou的步骤1消耗的时间T1, 工人完成的时间T2,如果T2

  所以很多条件都没有限制。

Leave a Reply

Your email address will not be published.