你们谁有用 Java8 的 list 查询过时间段重叠的对象集合吗？ 像是 List<item>,Item.startTime,Item.endTime,item1 和 item2 或者 itemN 可能有重叠的时间， 我的方法要遍历好几遍，效率太低了 嘤嘤嘤</item>
This topic created in 2948 days ago, the information mentioned may be changed or developed.
 |
debuggerxOct 8, 2018
1
为什么要遍历好几遍
不就是一遍排序再来一次遍历判断么 |
 |
polytheneOct 8, 2018
2
如果插入和查询都比较多，可以考虑用树结构
|
 |
jmc891205Oct 8, 2018
3
线段树？
|
 |
killpandaOct 8, 2018
4
使用 interval tree
|
 |
aisibiOct 8, 2018
5
做过类似的比较, 我的做法是把日期时间段格式化为例如 2018-07-05,2018-07-09
然后 add 到 List<String> 中, 然后直接排序, Collections.sort 然后比较上一个 endDate 与当前的 startDate |
 |
raysmondOct 8, 2018
7
不是按照 startTime 一遍排序，然后一次遍历取出所有重叠时间段吗？
|
 |
woodensailOct 8, 2018
9
@Breadykid 首先按开始时间从小到大排序，然后依次比较每一个时间段的结束时间与下一个时间段的开始时间，如果大于则有重叠。
|
 |
no1xsyzyOct 8, 2018
10
所有重叠对最低应该是 O(n log n) ？有更小的吗？
一种 startTime 排序后每轮之后的全部二分找当前的 endTime，需要所有的重叠对都产生的话可能掉到 n^2 …… List 实现是链表的话不能二分，可能需要搜索树？ 另一种预处理将所有时间变为离散的然后做桶，会产生重复对需要 uniq。 |
 |
12
@woodensail 就是，如果有多个重叠的话，是不是要遍历多次哇？
|
|
woodensailOct 8, 2018
13
看你需求是啥了，我目前遇到的需求都是冲突提示，只要遇到第一个冲突就停止检查并提示。
|
Select Language