如何计算两次在场的最少人数
我会尽我所能做到的。
我有一个活动有两次，开始和结束。(时间为24小时格式)例如，此事件从8开始，结束于12。
在这次活动中，我有一份列有他们工作日程的人的名单。下面是一个例子：
- 人1: 8:00至10:00
- 人2: 10:00至12:00
- 人3: 6:00至3:00
- 人4: 8:00至9:00
- 第5人: 9:30至12:00
现在，我需要知道有多少人，至少，我有通过整个事件。
在我的例子中，它将是2，因为：
- 人1和人2相辅相成
- 第三人永远都在
- 在4和5之间，9:00到9:30之间有一种喘息，所以在这段时间里，4和5人之间没有人会出现。
如果我用时间来解释这一点：
- 8:00至9:00 :第1、3、4人
- 9:00至9:30 :第一人，第三人
- 9:30至10:00 :第1、3、5人
- 上午10:00至中午12:00 :第2、3、5人
大多数情况下，活动将有3人，但最低的如果2人。
我怎么能用算法得到这个数字，我不能用这个来决定我的想法。
我考虑以分钟为单位转换时间(我不会低于分钟)，在活动时间设置范围(从8*60到12*60)，并将每个人的出现添加为新的范围，然后计算每分钟有多少片(1片=1人)。但是我觉得这样做是没有效率的，因为我需要数4*60分钟的切片:/ (从8 -> 12开始)。
你会怎么做？
回答 5
Stack Overflow用户
发布于 2012-08-10 12:18:18
取个人编号i的开始和结束时间，并将它们命名为s_i和e_i。
把所有这些都列在一个列表中，times。然后执行以下操作：
# start_time contains the start time of the event
# end_time contains the start time of the event
sort(times) # When doing this sort, make sure that if a s_i
# is at the same time as a e_j, put the s_i first.
current_number = number of people who're there at start_time
remove all times that match start_time from times
minimum_number = current_number
for time in times:
if time is an s_i: current_number += 1
if time is an e_i:
current_number -= 1
if current_number < minimum_number and time < end_time:
minimum_number = current_number运行时间如下：
让n是人数。
我们花费O(n lg n)时间进行排序，因为我们只有2n时间来排序。
然后，我们花费O(n)时间迭代时间，做持续的工作。
总的来说，O(n lg n)。请注意，这个运行时间完全独立于它跨越的时间间隔有多大，并且只取决于您处理的人员数量。
这是扫描线算法的一种形式。我们横扫整个时代，只停留在感兴趣的地方( s_i和e_i)。
注意，对于领带，我们在s_is之前对e_js进行排序的原因如下：
如果我们不这样做，那么想象一下我们有两个人:鲍勃在8-10，爱丽丝从10-12在这里。然后，如果不仔细排序，我们可能会得到以下时间列表：
times = [(s_Bob, 8), (e_Bob, 10), (s_Alice, 10), (e_Alice, 12)]如果我们这样分类，那么在鲍勃10点离开之后，就没有人留下了。然而，爱丽丝在那里，因为她是同时到达的。因此，为了防止出现这种情况，我们将其排序为:开始时间在结束时间之前，如果有领带，则为：
times = [(s_Bob, 8), (s_Alice, 10), (e_Bob, 10), (e_Alice, 12)]Stack Overflow用户
发布于 2012-08-10 12:15:27
快速回答，也许在某人开始/完成工作时更新人数？
例如，在t0，您设置它是为了知道谁在那里。每隔一分钟，或更好，每一个休假/入职日期(排序)注意到新的人数的现职人员。
Stack Overflow用户
发布于 2012-08-10 12:26:38
如果你的活动中没有太多的人，你可以去做这样的事情
minimum -> infinity
for each person in persons do:
intersections -> 0
for each other person in persons do:
if other person start time <= person start time
if other person end time >= person start time
intersections++
else if other person start time < person end time
intersections++
if intersections < minimum
minimum = intersectionshttps://stackoverflow.com/questions/11901406
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号