a******8
发帖数: 90 | 1 1月面的：2个list里面装的interval, 判断后1个是前1个的sub interval,就是前1个
list的interval完全能包含后一个list的interval.2个list没排序,什么都没做。
我当时想的是sort基于start,然后merge,然后判断，不过说的时候总被老印打断，这个
只会java的老印不让我用C++的sort(),我当时都把compare()函数写了，然后又争了些
东西，我思路都说完了，不过代码没写完，看看大家有什么想法 | p*****p
发帖数: 379 | 2 没太看懂你题目的意思，不过感觉不需要排序，开一个list装list1的interval，然后
扫2判断
O(m+n)，排序肯定超过这个
【在 a******8 的大作中提到】
: 1月面的：2个list里面装的interval, 判断后1个是前1个的sub interval,就是前1个
: list的interval完全能包含后一个list的interval.2个list没排序,什么都没做。
: 我当时想的是sort基于start,然后merge,然后判断，不过说的时候总被老印打断，这个
: 只会java的老印不让我用C++的sort(),我当时都把compare()函数写了，然后又争了些
: 东西，我思路都说完了，不过代码没写完，看看大家有什么想法
| f*******t
发帖数: 7549 | | j*****y
发帖数: 1071 | 4 bless
list里面的每个 node 对应一个 interval吗？ 两个list 的长度是一样的吗？
判断后一个是前一个的sub-interval,这个什么对应关系？ list 1的第一个 interval
包含 list 2的第一个interval ?
【在 a******8 的大作中提到】
: 1月面的：2个list里面装的interval, 判断后1个是前1个的sub interval,就是前1个
: list的interval完全能包含后一个list的interval.2个list没排序,什么都没做。
: 我当时想的是sort基于start,然后merge,然后判断，不过说的时候总被老印打断，这个
: 只会java的老印不让我用C++的sort(),我当时都把compare()函数写了，然后又争了些
: 东西，我思路都说完了，不过代码没写完，看看大家有什么想法
| s*****1
发帖数: 134 | 5 我也是这么想的，先sort,再merge, 不过这个思路好像不太对额~
list1 (1,4)(2,5)
list2 (1,5)
按照这个思路，list2是能放进list1去的，因为list1 merge完后是(1,5)
但是实际上 (1,5)放不到以上任何一个去额
【在 a******8 的大作中提到】
: 1月面的：2个list里面装的interval, 判断后1个是前1个的sub interval,就是前1个
: list的interval完全能包含后一个list的interval.2个list没排序,什么都没做。
: 我当时想的是sort基于start,然后merge,然后判断，不过说的时候总被老印打断，这个
: 只会java的老印不让我用C++的sort(),我当时都把compare()函数写了，然后又争了些
: 东西，我思路都说完了，不过代码没写完，看看大家有什么想法
| G****A
发帖数: 4160 | 6 interval都是integer么?
inclusive or exclusive?
求得是sub interval还是overlap?
如果求得的是sub interval，list2只找最左点、最右点。然后scan一遍list1就行了。
线性复杂度应该能搞定
【在 a******8 的大作中提到】
: 1月面的：2个list里面装的interval, 判断后1个是前1个的sub interval,就是前1个
: list的interval完全能包含后一个list的interval.2个list没排序,什么都没做。
: 我当时想的是sort基于start,然后merge,然后判断，不过说的时候总被老印打断，这个
: 只会java的老印不让我用C++的sort(),我当时都把compare()函数写了，然后又争了些
: 东西，我思路都说完了，不过代码没写完，看看大家有什么想法
| s****0
发帖数: 117 | 7 我也觉得是这个。
每个节点存中心和长度。
【在 f*******t 的大作中提到】
: interval tree
| c********t
发帖数: 5706 | 8 为什么要开一个新的list来装list1? 扫2对应list1查询，最后难道不是O(m*n)吗？
interval tree好复杂，能40分钟写出来吗？
【在 p*****p 的大作中提到】
: 没太看懂你题目的意思，不过感觉不需要排序，开一个list装list1的interval，然后
: 扫2判断
: O(m+n)，排序肯定超过这个
| p*****2
发帖数: 21240 | | f*******t
发帖数: 7549 | 10 搞竞赛的10分钟
【在 c********t 的大作中提到】
: 为什么要开一个新的list来装list1? 扫2对应list1查询，最后难道不是O(m*n)吗？
: interval tree好复杂，能40分钟写出来吗？
| h*******e
发帖数: 1377 | 11 请重新解释题。 感觉楼主表达是 一个list 就1个interval？
结果要求什么重新排列 两个list 里的 element 还是 merge 两个list 。。 |
|
