我试图解决以下问题:给定N个时间间隔,每个时间间隔指定为(开始,结束),不重叠,根据开始排序——找到一个包含给定日期的时间间隔。例如:
[1,4] [5,8] [9,10][11,20]
3人进入第一节,15人进入第四节,以此类推。
到目前为止,我有以下基本想法:
我在想,这两种方法是否有结合的余地。另一个想法是根据持续时间进行排序,并将所有间隔插入到树中,通过开始日期进行比较,这在最坏的情况下,当最长持续时间按时间顺序排列时,这种方法的性能相当于2。
我设想的理想解决方案是有一棵树(或一些类似的数据结构),树的顶部包含最长的间隔,然后两个分支将有接下来的两个最长间隔等。然而,我认为没有办法在树中分支,也就是说,因为我们明确假设我们根据长度插入,我们不能真正抛弃树的左边或右边。
如有任何评论,将不胜感激。
把两者结合起来是可能的。这是我的想法,
建立一个基于范围长度的二叉树,假设我们有以下范围,
a:[0,1]、b:[1,2]、c:[3,10]、d:[11,12]、e:[13,14]
我们从底部建造树,我们根据范围大小组合叶子,所以第一轮我们可以得到内部叶子,
(a,b),c,(d,e)
然后
(a、b、c)、(d、e)
根将是,
(a、b、c、d、e)
在每一轮中,我们将范围长度最小的节点组合在一起,保持树的深度。
每个节点指向左、右子节点,并保持子节点的最小、最大值。
如有不妥,请指出。
您可以在二叉搜索树中对某些节点进行优先级排序,并保持其平衡:
从你的组合方法开始(将更长的间隔放在更靠近顶部的位置),并采用一系列轮换来平衡二叉搜索树(在打破一些优先级的同时,如果没有打破平衡,它应该保留靠近根的高优先级节点)。
要平衡一棵树,试试这个策略(未经测试):
这应该产生一个AVL平衡树,尽可能尊重原始优先级。
这两种方法的简单组合在大多数情况下提供了一个O(1)
,在最坏的情况下提供了O(logN)
,但大O符号中的隐藏常数将是两倍:
间隔
长度
间隔
中进行搜索,使用线性搜索在长度
中进行搜索。搜索将并行进行1,第一个搜索完成后,另一个搜索也将停止
因为在步骤3中,我们可以在间隔中执行多达
c*log(n)
的二进制搜索步骤,我们总共将执行多达2*c*log(n)
的步骤。如果在<代码>长度<代码>中找到元素更快,它将导致二进制搜索在中间结束,并且我们将得到减少的操作数,(但具有双常数,然后是原来的方法)。
(1)不需要并行计算机,可以通过在每个步骤中搜索一个步骤来实现,在单个线程上模拟并行计算,直到找到答案。(一般信息,不需要理解答案:“并行搜索”的概念是由伊文、伊泰和沙米尔在他们的文章《时间表的复杂性和多商品流动问题》中介绍的)
间隔有开始和结束时间。间隔可能重叠。可能有几个包含时间t的间隔。只返回其中一个就可以了。 这是一个面试问题。我能够解决这个问题,方法是根据结束对间隔进行排序,根据开始对另一个时间进行排序,并取具有匹配开始和结束的间隔的交点。显然有更多优化的解决方案。 这里有一个例子:[1,5][2,10][3,6][2,9],目标是8。在这种情况下,[2,10]和[2,9]中的任何一个都是正确答案。 我想问题的关
问题内容: 我有下表,其中包含每15分钟从几个不同的设备读取的值: 我想在表中找到每个月在给定月份中没有条目的所有设备的所有差距。对于上表,结果应该是这样的: 该表大约有35000台设备和1亿个条目。 这是我尝试过的;它很慢,但是返回我需要的。但是,除了速度之外,还有另一个问题:它只能找到在给定月份设备的最后一个条目之前丢失的时间间隔;之后的所有内容都将被忽略,因此有可能会错过额外的缺失值间隔。
我的用例——我是一名医生。在某一天,我可以工作几个小时,但有些时间不可用。我想创建一个对象“周期我的工作日”。当有人预约上午8点到9点(即“周期病人1预约”)时,该时段将从我的工作日“删除”。当新患者访问myWorkDay时,他只看到myWorkDay-病人1约会。如果病人1释放了他的时隙,那么新患者会看到完整的myWorkDay。 有可能使用JodaTime做到这一点吗? 有一个额外的要求是不必
问题内容: 我需要更改此代码,以使X轴包含格式为“ H:M”的时间戳,例如10:00。 问题答案: 使用与合适的轴:
假设我有一个这样的范围列表 现在我想找到一个范围,比如。我的算法应该给我这个范围的所有范围。例如,这个的输出应该是 <代码>输出-[1,3]、[2,5]、[4,6]、[8,10] 我该如何着手解决这个问题? PS:我知道段树可能会有所帮助。我可以在其中构建树来存储间隔并查询位于间隔内的Point,但如何在给定间隔的情况下获取所有间隔。
# interval(date) Alias for interval.floor(date). For example, d3.time.day(new Date()) returns midnight (12:00 AM) on the current day, in local time. # interval.floor(date) Rounds down the specified da