最大访客数

来自计算思维百科
跳转至: 导航搜索
最大访客数1.png

现将举行一个聚会,让访客事先填写到达时间和离开时间,为了掌握座位的数目,必须先估计不同时间的最大访客数。

假设聚会共邀请了5个人,5个人的到达时间与离开时间登记如下:

访客

到达时间

离开时间

1

7:00

7:30

2

7:00

7:50

3

7:10

9:00

4

7:30

8:10

5

7:50

7:40

 

解决方案

方案1-蛮力法求最大访客数

若求7:50的访客数,需要查看每位访客的到达时间与离开时间。

访客1在7:30离开,记为0

访客2 在7:50 离开,记为0

访客3 在7:50前到达,7:50后离开,记为1

访客4 在7:50前到达,7:50后离开,记为1

访客5 在7:离开,记为0

则7:50的访客数为1+1=2.

方案2-变治法求最大访客数

利用ArriverTime[ i ]来记录第i个访客的到达时间,LeaveTime [i]记录第i个访客的离开时间,则可以得到结果如下:

访客到达时间与离开时间记录

访客i

1

2

3

4

5

ArriveTime[i]

7:00

7:00

7:10

7:30

7:50

LeaveTime[i]

7:30

7:50

9:00

8:10

7:40

我们按照先后顺序排序,则有

按时间先后排序的到达时间与离开时间记录

ArriveTime

7:00

7:00

7:10

7:30

7:50

LeaveTime

7:30

7:40

7:50

8:10

9:00

此时我们求7:50的访客数,只需找出在ArriveTime不大于7:50的访客有多少,可以看到有5个;再查LeaveTime小于7:50的访客有多少,可以看到前3个;

最大访客数2.png

所以访客数等于5-3=2.

涉及到的计算思维

蛮力法解决这个问题的很直接的方法就是考虑同一个访客的到达时间和离开时间,这种做法通过计算机的机械化思维方式来解决,可是比较复杂;变治法是将来访时间与离开时间分开处理会使得求解过程更简单。即将来访时间和离开时间分别排序。然后计算同一时刻前的(到达访客-离开访客),就可以计算出这一时刻的访客数,将结果排序即可获得最大访客数。在这个过程中,我们可以发现后者采用了变治法的思想将原本复杂的问题转化成了简单易处理的问题,体现了计算思维中的转化思想。