1

假设我有一份人员名单，其中列出了他们在过去发生的事件中的到达和离开时间。

我的任务是找出在任何时候参加活动的最大人数？我没有得到查询时间。

ai = 人 i 的到达时间

di = 人 i 的出发时间

我有一个列表，如 (a1,d1)、(a2,d2)、(a3,d3).... (an,dn)... 它不在数据库中。

在此处输入图像描述

在这个问题中，我们可以看到事件的最大人数是 3。
所以在这个例子中。对于大小为 3 的问题，我们有五个解决方案。{b,d,e}, {j,h,i}, {c,b,a}, {e,g,f}, {g,h,f} . 我只想知道3号。

我的方法：
我。创建一个大小 = 上次出发时间 - 首次到达时间的数组。并不断增加该数组的计数。
ii. 我试图按人们的开始时间对他们进行排序。并继续跳到下一个人的开始时间。在那之后我迷路了。我该如何进行。

谢谢

@ypnos : //根据时间戳对数据进行排序。

int count = 0;
int max = 0
char [] arr = {a1, a2, d1, a3, a4, d3, d2, } like this..
for(int i =0; i < arr.length; i++)
{
    if(arr[i].startswith('a') ) 
    {
         count++;
    if(count > max)
    {
        max = count;
    }
    }
    else
   {
    count--;
   }
}
4

4 回答 4

6

首先，您创建一个包含到达和离开时间的排序列表。它是两个事件的单个列表，每个事件都包含一个时间戳（排序键是什么）和一个布尔值（到达或离开）。

新解决方案（找到最大值）：

然后你可以遍历你的列表，记住每个条目的当前数字并相应地增加/减少它，同时如果合适的话还更新你的最大数字。

排序：O(N log N)，找到最大值。数量：O(N)

由于问题中措辞不当而导致的旧解决方案（在时间 X 查询）：

获得该列表后，您可以创建一个地图，其中包含时间戳作为键，并将当前时间戳的人数作为数据。要创建它，您需要浏览您的排序列表，记住每个条目的当前数字并相应地增加/减少它，同时还将元素添加到您的地图中。

现在您有了地图，您可以通过在地图中搜索查询时间戳左侧的元素轻松找到正确的数字。

对于地图，我的意思是二叉树，或者 std::map 的基础是什么。顺便提一句。std::map 为您提供了 lower_bound() 函数来执行此操作（ref）。

但是，自己实现二叉树并不难。现在对于操作的成本：每个条目 O(log N)，每个查询 O(log N)。

于 2013-03-01T23:58:13.713 回答
0

这是在数据库中吗？如果是这样，您只需选择到达时间 < 现在 < 出发时间的行。

这是一件简单的事情，但我们需要知道您使用什么数据结构来保存数据以提供特定的解决方案。

方法很简单：一个字典数组，其中每个字典由到达：值和出发：值组成。然后在任何给定时间，您迭代数组，如果：到达 < 现在 < 出发 == TRUE，则增加一个计数器。

完毕。

于 2013-03-01T23:51:51.923 回答
0

遍历列表，测试给定时间t是否在当前对的到达和离开之间，如果是，则增加一个计数器。之后，您的柜台应该有正确的号码。伪代码：

given time T
given list of (arrival, departure) pairs L

c = 0
for each pair (A, D) in L
    if A < T and T < D
        c += 1

请注意，这不是最佳解决方案...将数据存储在更适合查询的结构中将实现更有效的解决方案。

于 2013-03-01T23:55:23.833 回答
0

在 SQL 中？

SELECT count(id) FROM attendee WHERE a_time < '2013-03-01 12:12' AND (d_time > '2013-03-01 12:12' OR d_time IS NULL)
于 2013-03-01T23:55:41.487 回答