小编Ste*_*e M的帖子

给你一组间隔S.您必须在最小时间复杂度中找到S包含在给定时间间隔内的所有时间间隔(a, b).

这可以O(n)通过蛮力及时完成,其中n是集合中的间隔数S.但如果我被允许做一些预处理,这可以在不到O(n)时间的O(log n)时间内完成吗？

最初我在考虑区间树,但我不认为它适用于此,因为区间树用于获取与给定区间重叠的所有区间.