这是一个创建于 2236 天前的主题，其中的信息可能已经有所发展或是发生改变。
你们谁有用 Java8 的 list 查询过时间段重叠的对象集合吗？ 像是 List<item>,Item.startTime,Item.endTime,item1 和 item2 或者 itemN 可能有重叠的时间， 我的方法要遍历好几遍，效率太低了 嘤嘤嘤</item>
 |
1
debuggerx 2018-10-08 13:27:35 +08:00
为什么要遍历好几遍
不就是一遍排序再来一次遍历判断么 |
 |
2
polythene 2018-10-08 13:31:22 +08:00
如果插入和查询都比较多，可以考虑用树结构
|
 |
3
jmc891205 2018-10-08 13:31:29 +08:00
线段树？
|
 |
4
killpanda 2018-10-08 13:32:44 +08:00
使用 interval tree
|
 |
5
aisibi 2018-10-08 14:28:13 +08:00
做过类似的比较, 我的做法是把日期时间段格式化为例如 2018-07-05,2018-07-09
然后 add 到 List<String> 中, 然后直接排序, Collections.sort 然后比较上一个 endDate 与当前的 startDate |
 |
7
raysmond 2018-10-08 14:47:04 +08:00
不是按照 startTime 一遍排序，然后一次遍历取出所有重叠时间段吗？
|
 |
8
Breadykid OP @raysmond 一次遍历怎么取所有的重叠？可能 item1，item2，item3 重叠，然后 item4，item5 重叠这样
|
 |
9
woodensail 2018-10-08 15:10:14 +08:00
@Breadykid 首先按开始时间从小到大排序，然后依次比较每一个时间段的结束时间与下一个时间段的开始时间，如果大于则有重叠。
|
 |
10
no1xsyzy 2018-10-08 15:54:58 +08:00
所有重叠对最低应该是 O(n log n) ？有更小的吗？
一种 startTime 排序后每轮之后的全部二分找当前的 endTime，需要所有的重叠对都产生的话可能掉到 n^2 …… List 实现是链表的话不能二分，可能需要搜索树？ 另一种预处理将所有时间变为离散的然后做桶，会产生重复对需要 uniq。 |
|
12
Breadykid OP @woodensail 就是，如果有多个重叠的话，是不是要遍历多次哇？
|
|
13
woodensail 2018-10-08 17:25:50 +08:00
看你需求是啥了，我目前遇到的需求都是冲突提示，只要遇到第一个冲突就停止检查并提示。
|
Select Language