首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
拉钩
V2EX  ›  Java

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

  •  
  •   Breadykid · 64 天前 · 1266 次点击
    这是一个创建于 64 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    13 回复  |  直到 2018-10-08 17:25:50 +08:00
        1
    debuggerx   64 天前
    为什么要遍历好几遍
    不就是一遍排序再来一次遍历判断么
        2
    polythene   64 天前
    如果插入和查询都比较多,可以考虑用树结构
        3
    jmc891205   64 天前
    线段树?
        4
    killpanda   64 天前
    使用 interval tree
        5
    aisibi   64 天前
    做过类似的比较, 我的做法是把日期时间段格式化为例如 2018-07-05,2018-07-09
    然后 add 到 List<String> 中, 然后直接排序, Collections.sort
    然后比较上一个 endDate 与当前的 startDate
        6
    Breadykid   64 天前
    @jmc891205 素的
        7
    raysmond   64 天前
    不是按照 startTime 一遍排序,然后一次遍历取出所有重叠时间段吗?
        8
    Breadykid   64 天前
    @raysmond 一次遍历怎么取所有的重叠?可能 item1,item2,item3 重叠,然后 item4,item5 重叠这样
        9
    woodensail   64 天前
    @Breadykid 首先按开始时间从小到大排序,然后依次比较每一个时间段的结束时间与下一个时间段的开始时间,如果大于则有重叠。
        10
    no1xsyzy   64 天前
    所有重叠对最低应该是 O(n log n) ?有更小的吗?
    一种 startTime 排序后每轮之后的全部二分找当前的 endTime,需要所有的重叠对都产生的话可能掉到 n^2 …… List 实现是链表的话不能二分,可能需要搜索树?
    另一种预处理将所有时间变为离散的然后做桶,会产生重复对需要 uniq。
        11
    Breadykid   64 天前
    @no1xsyzy emmmmmmm,看上去处理的小复杂。。。
        12
    Breadykid   64 天前
    @woodensail 就是,如果有多个重叠的话,是不是要遍历多次哇?
        13
    woodensail   64 天前
    看你需求是啥了,我目前遇到的需求都是冲突提示,只要遇到第一个冲突就停止检查并提示。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   871 人在线   最高记录 4019   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 18ms · UTC 19:23 · PVG 03:23 · LAX 11:23 · JFK 14:23
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1