这道linkedin题是不是应该用segment tree?# JobHunting - 待字闺中
J*v
1 楼
Decide whether a target is covered by a list of intervals
J*v
2 楼
还是用merge intervals
s*g
3 楼
interval tree?
c*t
4 楼
Traveling intervals doesn't work?
【在 J*****v 的大作中提到】
: 还是用merge intervals
【在 J*****v 的大作中提到】
: 还是用merge intervals
J*v
5 楼
可以先merge，再看merged之后的区间没有包含给定的target区间，这样得花o(nlogn)
时间。
不过segment tree往往能给出最好的解法
【在 c********t 的大作中提到】
: Traveling intervals doesn't work?
时间。
不过segment tree往往能给出最好的解法
【在 c********t 的大作中提到】
: Traveling intervals doesn't work?
s*g
6 楼
segment tree的空间cost未必能太好
【在 J*****v 的大作中提到】
: 可以先merge，再看merged之后的区间没有包含给定的target区间，这样得花o(nlogn)
: 时间。
: 不过segment tree往往能给出最好的解法
【在 J*****v 的大作中提到】
: 可以先merge，再看merged之后的区间没有包含给定的target区间，这样得花o(nlogn)
: 时间。
: 不过segment tree往往能给出最好的解法
c*t
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往往能给出最好的解法
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
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
能用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
相关阅读
Accenture的contractor机会，银行驻场网络安全工程师FLGU面经贴签了offer还能要求加钱么this is really awesome.诚心请教: 面试之后被要求提供现在公司的paystub可以不给吗关于opt的问题Snapchat黄了？微软是不是在中国混得最好的IT公司？ (转载)有人是四大的吗？求内推！g家L 6/7对应fb是啥？OPT 两个月了， 还没批， 加急失败，求助最近所有onsite的题都做出来了报个亚麻包裹+面经 同时求建议大家当码农的有像我这样不管任务催的多紧 到点就走人的吗H1被雷填gap转B2和转H4可有什么差别？辞职信都递了，老板还不停的给我分配新任务进了flag，发现能力不行，是不是马上就被fire了？请教一下LinkedIn offer negotiation实习的return offer能negotiate工资吗？netflix 招人的要求