0

我会尽可能清楚。

我有一个事件有两次，开始和结束。（时间为 24 小时制）例如，此事件从 8 点开始，到 12 点结束。

在这个活动中，我有一份人员名单和他们的工作时间表。这是一个例子：

  • 人 1 : 从 8:00 到 10:00
  • 人 2 : 从 10:00 到 12:00
  • 3人：从6:00到15:00
  • 4人：从8:00到9:00
  • 5人：从9:30到12:00

现在，我需要知道至少有多少人参加了整个活动。

就我而言，它将是2，因为：

  • 第 1 人与第 2 人相辅相成
  • 人 3 将永远在场
  • 在 9:00 到 9:30 之间，第 4 和第 5 个人之间有喘息声，因此在此期间，第 4 和第 5 个人之间不会有人在场。

如果我用时间解释这一点：

  • 从 8:00 到 9:00 : 人 1, 3, 4
  • 从 9:00 到 9:30 : 人 1, 3
  • 从 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）。

你会怎么做？

4

5 回答 5

2

取人号的开始时间和结束时间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). 请注意，此运行时间完全独立于它跨越的时间间隔有多大，并且仅取决于您正在处理的人数。

这是扫线算法的一种形式。我们穿越时代，只停留在兴趣点（the s_iand e_is.）

请注意，如果出现平局，我们将 s 排序在s_is 之前的原因e_j如下：

如果我们不这样做，那么想象我们有两个人：Bob 从 8 点到 10 点在这里，Alice 从 10 点到 12 点在这里。如果我们不仔细排序，我们可能会得到以下时间列表：

times = [(s_Bob, 8), (e_Bob, 10), (s_Alice, 10), (e_Alice, 12)]

如果我们这样排序，那么看起来 Bob 10 点离开后就没有人了。但是，Alice 在那里，因为她同时到达。因此，为了防止这种情况，我们对它进行排序，使得开始时间在结束时间之前，以防出现平局：

times = [(s_Bob, 8), (s_Alice, 10), (e_Bob, 10), (e_Alice, 12)]
于 2012-08-10T12:18:18.480 回答
0

快速回答，也许每当有人开始/完成工作时更新人数？

例如，在 t0 时，您将其设置为知道谁在那里。每隔一分钟，或者更好，对于每个离开/进入日期（排序），请注意新的出席人数。

于 2012-08-10T12:15:27.243 回答
0

我认为你的算法应该这样设计：

  • 从 8:00 开始：第 1、3、4 人
  • 从 9:00 开始：第 1 人、第 3 人
  • 从 9:30 开始：第 1、3、5 人
  • 从 10:00 开始：第 2、3、5 人

首先将事件的开始和结束时间添加到集合中 接下来，遍历您的成员，构建一组开始和结束时间（集合防止重复）。然后遍历集合中的项目，并针对集合中的每个元素检查每个成员，以查看他的开始时间是否 >= 并且结束时间 > 然后是集合中的项目。有一个内部迭代的计数器来跟踪给定时间的人数，并在两个迭代之外有一个变量来跟踪给定时间的最小人数。在伪代码中：

var set : set
var event_start : time = 8:00
var event_end : time = 12:00
set.add(event_start)
foreach(person in people)
    set.add(person.start)
    set.add(person.end)
var min : int = people.size
var time_of_min : time
foreach time in set
    var num_people : int = 0
    foreach person in people
        if person.start >= time && person.end > time
            num_people++
    if num_people < min
        min = num_people
        time_of_min = time
// Handle the special case of the ending time
var num_people_at_end : int = 0
foreach person in people
    if person.end == event_end
        num_people_at_end++
if num_people_at_end < min
    min = num_people_at_end
    time_of_min = event_end
于 2012-08-10T12:32:26.563 回答
0

如果您的活动中没有太多人，您可以去做类似的事情

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 = intersections
于 2012-08-10T12:26:38.587 回答
0

hauron 的回答帮助我创建了这个解决方案。

这是伪代码，因为没有语言标签。

有一个排序的开始时间列表和一个排序的结束时间列表
在零开始当前人员
的计数器 还有一个正无穷大的最小人员计数器 将最近时间作为事件的初始时间

一起浏览列表，选择第一个开始时间和第一个结束时间中较早的一个

如果开始时间越早，则增加计数器并删除第一个开始时间 否则结束时间越早，减少计数器并删除第一个结束时间

如果刚刚使用的时间和最近的时间不一样，检查最小人数计数器（例如，如果3个人同时进入，等待更新最小人数计数器，直到处理所有三个人）如果当前人数较少比最小人数，设置最小人数为当前人数

更新最近一次
重复直到两个列表都为空

最少的人数计数器应该有你的答案

于 2012-08-10T12:31:58.790 回答