给定一组间隔S.您必须在最小时间复杂度中找到S中包含在给定间隔(a,b)中的所有间隔
Ste*_*e M 5 algorithm tree search intervals data-structures
给你一组间隔S.您必须在最小时间复杂度中找到S包含在给定时间间隔内的所有时间间隔(a, b).
这可以O(n)通过蛮力及时完成,其中n是集合中的间隔数S.但如果我被允许做一些预处理,这可以在不到O(n)时间的O(log n)时间内完成吗？
最初我在考虑区间树,但我不认为它适用于此,因为区间树用于获取与给定区间重叠的所有区间.
您可以在2D平面中重新构建问题.让(begin, end)每个区间的是一个二维点.(请注意,所有有效间隔都将在对角线上方结束)
您的Interval-search-problem转换为经过充分研究的正交2D范围查询,其算法具有 要么
运行时,其中k是报告的点数.
