题
我已经有了一个类代表一个时间间隔。这类具有两种性质"开始"和"结束"的一个可比较的类型。现在我在寻找一个高效率的算法,采取联盟的一套这样的时间间隔。
在此先感谢。
解决方案
按照其中一个术语(例如,开始)对它们进行排序,然后在列表中移动时检查与其(右手)邻居的重叠。
class tp():
def __repr__(self):
return '(%d,%d)' % (self.start, self.end)
def __init__(self,start,end):
self.start=start
self.end=end
s=[tp(5,10),tp(7,8),tp(0,5)]
s.sort(key=lambda self: self.start)
y=[ s[0] ]
for x in s[1:]:
if y[-1].end < x.start:
y.append(x)
elif y[-1].end == x.start:
y[-1].end = x.end
其他提示
使用扫描线算法。基本上,您对列表中的所有值进行排序(同时保持区间的开始或结束以及每个项目)。该操作是O(n log n)。然后沿着已排序的项循环一次,并计算间隔O(n)。
O(n log n)+ O(n)= O(n log n)
事实证明这个问题已经解决,多次--在不同程度的幻想,将根据nomenclature(s): http://en.wikipedia.org/wiki/Interval_tree , http://en.wikipedia.org/wiki/Segment_tree 和也RangeTree'
(如运的问题,涉及大型计数的时间间隔,这些数据结构问题)
在我自己的选择的蟒蛇图书馆选择:
从测试,我发现,大多数指甲这方面正在全功能和python流(无位腐烂):该'隔'和'联盟'类SymPy,见: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/
另一个好看的选择、高性能,但不太丰富的功能选择(例如。没有工作上的浮点的范围内去除): https://pypi.python.org/pypi/Banyan
最后:搜查周边所本身在任何IntervalTree,SegmentTree,RangeTree,你会找到答案/钩进一步丰富
geocar算法在以下情况下失败:
s=[tp(0,1),tp(0,3)]
我不太确定,但我认为这是正确的方法:
class tp():
def __repr__(self):
return '(%.2f,%.2f)' % (self.start, self.end)
def __init__(self,start,end):
self.start=start
self.end=end
s=[tp(0,1),tp(0,3),tp(4,5)]
s.sort(key=lambda self: self.start)
print s
y=[ s[0] ]
for x in s[1:]:
if y[-1].end < x.start:
y.append(x)
elif y[-1].end == x.start:
y[-1].end = x.end
if x.end > y[-1].end:
y[-1].end = x.end
print y
我也用它来实现减法:
#subtraction
z=tp(1.5,5) #interval to be subtracted
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)]
s.sort(key=lambda self: self.start)
print s
for x in s[:]:
if z.end < x.start:
break
elif z.start < x.start and z.end > x.start and z.end < x.end:
x.start=z.end
elif z.start < x.start and z.end > x.end:
s.remove(x)
elif z.start > x.start and z.end < x.end:
s.append(tp(x.start,z.start))
s.append(tp(z.end,x.end))
s.remove(x)
elif z.start > x.start and z.start < x.end and z.end > x.end:
x.end=z.start
elif z.start > x.end:
continue
print s
对所有点进行排序。然后通过列表递增“start”的计数器。点,并将其减少为“结束”点。如果计数器达到0,那么它实际上是联合中一个区间的终点。
计数器永远不会变为负数,并且会在列表末尾达到0。
在c ++中找到间隔联合的总和
#include <iostream>
#include <algorithm>
struct interval
{
int m_start;
int m_end;
};
int main()
{
interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } };
std::sort(
arr,
arr + sizeof(arr) / sizeof(interval),
[](const auto& i, const auto& j) { return i.m_start < j.m_start; });
int total = 0;
auto current = arr[0];
for (const auto& i : arr)
{
if (i.m_start >= current.m_end)
{
total += current.m_end - current.m_start;
current = i;
}
else if (i.m_end > current.m_end)
{
current.m_end = i.m_end;
}
}
total += current.m_end - current.m_start;
std::cout << total << std::endl;
}