J*****v
发帖数: 314 | 1 Decide whether a target is covered by a list of intervals |
J*****v
发帖数: 314 | |
s**********g
发帖数: 14942 | |
c********t
发帖数: 5706 | 4 Traveling intervals doesn't work?
【在 J*****v 的大作中提到】
: 还是用merge intervals
|
J*****v
发帖数: 314 | 5 可以先merge，再看merged之后的区间没有包含给定的target区间，这样得花o(nlogn)
时间。
不过segment tree往往能给出最好的解法
【在 c********t 的大作中提到】
: Traveling intervals doesn't work?
|
s**********g
发帖数: 14942 | 6 segment tree的空间cost未必能太好
【在 J*****v 的大作中提到】
: 可以先merge，再看merged之后的区间没有包含给定的target区间，这样得花o(nlogn)
: 时间。
: 不过segment tree往往能给出最好的解法
|
c********t
发帖数: 5706 | 7 哦，target是个区间啊
sort and merge. Then use binary search check. 其实time complexity 是一样的，
space complexity还更好 O(n)。我总觉得segment tree 没什么用。有没有哪道题需要
用segment tree?
A segment tree for a set I of n intervals uses O(n log n) storage and can be
built in O(n log n) time
【在 J*****v 的大作中提到】
: 可以先merge，再看merged之后的区间没有包含给定的target区间，这样得花o(nlogn)
: 时间。
: 不过segment tree往往能给出最好的解法
|
s**********g
发帖数: 14942 | 8 leetcode常见题型的话
能用segment tree的题基本都有其他替代品
光说tree就有神马BIT tree啊啥的
但segment tree的确可以灵活解决不少问题
未必能提供面试时的最优solution
但能解决问题 complexity也不差
be
【在 c********t 的大作中提到】
: 哦，target是个区间啊
: sort and merge. Then use binary search check. 其实time complexity 是一样的，
: space complexity还更好 O(n)。我总觉得segment tree 没什么用。有没有哪道题需要
: 用segment tree?
: A segment tree for a set I of n intervals uses O(n log n) storage and can be
: built in O(n log n) time
|
