e********8
发帖数: 4 | 1 从网上看来的一道面经，不知道如何解最优，求大神指点。。。
给你一个java interface, 实现两个method，一个是void add interval(int from,
int to), 另一个是int getTotalLength()返回已有interval的总时间，当然，要考虑
overlapping。比如(1,5), (2, 6)的total length 是5.
不知道用什么样的data structure 去解决。 | a******1
发帖数: 20 | | l*3
发帖数: 2279 | 3 考虑如何向不交的interval集合里面插入一个新的interval。
leetcode上的题。
【在 e********8 的大作中提到】
: 从网上看来的一道面经，不知道如何解最优，求大神指点。。。
: 给你一个java interface, 实现两个method，一个是void add interval(int from,
: int to), 另一个是int getTotalLength()返回已有interval的总时间，当然，要考虑
: overlapping。比如(1,5), (2, 6)的total length 是5.
: 不知道用什么样的data structure 去解决。
| e********8
发帖数: 4 | 4 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
插入，都得O(n) 时间复杂度，会不会效率不高？
【在 l*3 的大作中提到】
: 考虑如何向不交的interval集合里面插入一个新的interval。
: leetcode上的题。
| e********8
发帖数: 4 | 5 能不能展开介绍下。。。谢谢！
【在 a******1 的大作中提到】
: segment tree.
| c*****m
发帖数: 271 | 6 如果https://leetcode.com/problems/insert-interval/的最好方法是O(N)的，那我觉
得也不会有Ｏ(logn)的方法了吧。不认为这题能用segment tree做，可能我对segment
tree的用法还不够了解
【在 e********8 的大作中提到】
: 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
: 插入，都得O(n) 时间复杂度，会不会效率不高？
| l*3
发帖数: 2279 | 7 也不能简单理解为O(n)，你可以用BST来存储interval，这样如果是要新添入一个
interval，就是O(log n)，如果是要修改并合并之前k个interval，那确实需要 O(k
log n)的运算量，但是好处是做完你少了k个interval。我觉得总的来说，至少粗浅的
想，是不会有更好的数据结构了 （up to log complexity），因为看上去至少你总是
要维护若干个不相交的interval的，
比如如果你当前的interval是[0,1], [2,3], [4,5], [6,7] 这种，那看上去只能分别
存了，没有什么好的方法可以节省时间和空间代价。
【在 e********8 的大作中提到】
: 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
: 插入，都得O(n) 时间复杂度，会不会效率不高？
| l*3
发帖数: 2279 | 8 我也不认为这种问题适合线段树来处理
线段树处理连续区间的问题比较好，区间断断续续的话感觉搞不动。 | A***s
发帖数: 879 | 9 如果存在的 interval 不能合并成一个，返回的 totalLength 该怎么定义呢？
比如已有 (1,5) (6,7)
【在 e********8 的大作中提到】
: 从网上看来的一道面经，不知道如何解最优，求大神指点。。。
: 给你一个java interface, 实现两个method，一个是void add interval(int from,
: int to), 另一个是int getTotalLength()返回已有interval的总时间，当然，要考虑
: overlapping。比如(1,5), (2, 6)的total length 是5.
: 不知道用什么样的data structure 去解决。
| r*******g
发帖数: 1335 | 10 我觉得这题就是Merge Intervals。两个办法，一个是bst维护独立的不同的interval，
每个node是一个interval，这个缺点是无法删除interval，因为interval已经被merge
在一起了，而且插入的code不好写，好处是，可以很快的获得TotalLength。另外一个
办法当然就是interval tree了，网上有详细方法，用最基本的interval tree就可以，
好处是，插入操作非常easy，坏处是，不同node之间其实可能会overlap，所以最后
merge的时候需要注意，merge的开销应该是O(N)吧。所以理论最快的是BST tree，但是
interval tree很容易写。
不知道segment tree怎么写。 | r*******g
发帖数: 1335 | 11 如果已经sorted了，binary search就可以获得新的interval应该插入的位置，所以这
题确实可能考察的就是leetcode insert interval原题。
【在 e********8 的大作中提到】
: 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
: 插入，都得O(n) 时间复杂度，会不会效率不高？
| w*******d
发帖数: 221 | 12 merge时用lazy delete＋pointer会快很多，否则还是O(n)
【在 r*******g 的大作中提到】
: 如果已经sorted了，binary search就可以获得新的interval应该插入的位置，所以这
: 题确实可能考察的就是leetcode insert interval原题。
| s********g
发帖数: 2 | 13 用bst, 每个节点存interval［low, high］。所要维护的属性是树里的父节点的low要
大于左子节点的high，父节点的high要小于右子节点的low。 每次插入新节点的时候比
较路径节点上的interval， 并且更新插入节点的low／high值. 比如输入节点为［1,5
］, ［7,9］, ［6,13］, ［4,7］。
插入第一个节点时，树结构为 ［1，5］；
插入第二个节点时，树结构为
［1， 5］
［7，9］
插入第三个节点时，树结构为
［1， 5］
［7， 9］
［6， 7］ ［9， 13］
[6, 13]与［7，9］比较的时候会裂变成两个节点：［6， 7］， ［9， 13］。
插入第四个节点时，树结构为
［1， 5］
［7， 9］
［6， 7］ ［9， 13］
［5， 6］
［4，7］与［1，5］比较的时候会变成［5，7］；［5，7］与［6，7］比较的时候会变
成［5，6］
每次插入复杂度为o(logN), 最后算总长度，遍历一次树就行，复杂度为o(N). 这个解
法有点类似于skyline的bst解法， http://www.shadabahmed.com/blog/2013/04/24/skyline-algorithm-a-binary-tree-approach/. 不同的是 skyline 的线段有不同的高度，这里的险段的高度默认为1. | r*******g
发帖数: 1335 | 14 你这个方法好，每插入一个interval时候不需要merge node, 而是把interval本身分裂
成多段。
不过用bst的问题就是不能删除interval，还是只有interval tree才能删除interval。
5
【在 s********g 的大作中提到】
: 用bst, 每个节点存interval［low, high］。所要维护的属性是树里的父节点的low要
: 大于左子节点的high，父节点的high要小于右子节点的low。 每次插入新节点的时候比
: 较路径节点上的interval， 并且更新插入节点的low／high值. 比如输入节点为［1,5
: ］, ［7,9］, ［6,13］, ［4,7］。
: 插入第一个节点时，树结构为 ［1，5］；
: 插入第二个节点时，树结构为
: ［1， 5］
: ［7，9］
: 插入第三个节点时，树结构为
: ［1， 5］
|
|
