这不是一个面试问题本身,因为我在我的项目中遇到过这个问题,但我认为这可能是一个不错的干预问题.
你有N对间隔,比如说整数.您需要在O(N)时间内识别出彼此重叠的所有间隔.例如,如果你有
{1,3} {12,14} {2,4} {13,15} {5,10}
答案是{1,3},{12,14},{2,4},{13,15}.请注意,您不需要对它们进行分组,因此结果可以按照示例中的任何顺序进行.
我刚刚投入O(N)时间因为KMP算法需要O(N)进行字符串搜索.:d
我想出的最好的,我现在在项目中使用的是O(N ^ 2).是的,蛮力非常难过,但没有人抱怨所以我不会重构它.:P仍然,我很好奇,如果一个更大的头脑有一个更优雅的解决方案.
有人知道interval treeC++中的任何好的实现吗？
显然,模板驱动的东西,更好的类似boost风格.
另一个问题 - 如果有人测试过,在std::vector实践中,基于分类的基本区间树实现是否可以击败通用区间树(使用O(lg)操作)？
我有一组时间间隔In =(an,bn).我需要运行大量的查找,我给了时间t并且需要快速返回包含t的间隔,例如,那些间隔使得<= t <= bn.
什么是良好的数据结构或算法？
如果重要,在我的情况下,an和bn是整数.