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本质就是个动态的有序数组 |