j******2
发帖数: 362 | 1 http://en.wikipedia.org/wiki/Interval_tree
读了半天interval tree的解释。有点不明白。把intervals merge起来，再用2分法就
很容易查一个点是否在里面了阿，为什么还要搞这个interval tree阿？什么情况下要
搞interval tree阿？ |
j*****n
发帖数: 1545 | 2 Interval tree 返回的是 所有 包括那个点的 interval.
我觉得挺有用的, 很多和 interval 有关的问题都能用到 interval tree. |
j******2
发帖数: 362 | 3 能举个例子吗？必须用interval tree的
【在 j*****n 的大作中提到】
: Interval tree 返回的是 所有 包括那个点的 interval.
: 我觉得挺有用的, 很多和 interval 有关的问题都能用到 interval tree.
|
j*****n
发帖数: 1545 | 4 我觉得很多 scheduling 的问题都会涉及到 找 overlap. 然后 interval tree 就能用
了。 当然不用也行，complexity就高很多。 |
m****l
发帖数: 61 | 5 面试真心用不到这个。
我面了6家onsite，几次跟interviewer说可以用segment tree，发现对方完全不知道什
么是segment tree。所有题目都可以贪心或者2分。
最失败的是我没记清楚细节，当场也实现不出来。。。
【在 j******2 的大作中提到】
: http://en.wikipedia.org/wiki/Interval_tree
: 读了半天interval tree的解释。有点不明白。把intervals merge起来，再用2分法就
: 很容易查一个点是否在里面了阿，为什么还要搞这个interval tree阿？什么情况下要
: 搞interval tree阿？
|
s**********1
发帖数: 58 | 6 Interval tree是个动态结果，可以增加删除interval，你说的merge起来的数组是不行
的。其实BST本质就是个动态的有序数组 |
