Java8 怎么从中查找重叠时间段啊啊啊啊啊啊啊啊啊

[Breadykid]

你们谁有用 Java8 的 list 查询过时间段重叠的对象集合吗？ 像是 List<item>,Item.startTime,Item.endTime,item1 和 item2 或者 itemN 可能有重叠的时间， 我的方法要遍历好几遍，效率太低了 嘤嘤嘤</item>

[debuggerx]

为什么要遍历好几遍
不就是一遍排序再来一次遍历判断么

[polythene]

如果插入和查询都比较多，可以考虑用树结构

[jmc891205]

线段树？

[killpanda]

使用 interval tree

[aisibi]

做过类似的比较, 我的做法是把日期时间段格式化为例如 2018-07-05,2018-07-09
然后 add 到 List<String> 中, 然后直接排序, Collections.sort
然后比较上一个 endDate 与当前的 startDate

[Breadykid]

@jmc891205 素的

[raysmond]

不是按照 startTime 一遍排序，然后一次遍历取出所有重叠时间段吗？

[Breadykid]

@raysmond 一次遍历怎么取所有的重叠？可能 item1，item2，item3 重叠，然后 item4，item5 重叠这样

[woodensail]

@Breadykid 首先按开始时间从小到大排序，然后依次比较每一个时间段的结束时间与下一个时间段的开始时间，如果大于则有重叠。

[no1xsyzy]

所有重叠对最低应该是 O(n log n) ？有更小的吗？
一种 startTime 排序后每轮之后的全部二分找当前的 endTime，需要所有的重叠对都产生的话可能掉到 n^2 …… List 实现是链表的话不能二分，可能需要搜索树？
另一种预处理将所有时间变为离散的然后做桶，会产生重复对需要 uniq。

[Breadykid]

@no1xsyzy emmmmmmm，看上去处理的小复杂。。。

[Breadykid]

@woodensail 就是，如果有多个重叠的话，是不是要遍历多次哇？

[woodensail]

看你需求是啥了，我目前遇到的需求都是冲突提示，只要遇到第一个冲突就停止检查并提示。