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

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

  •  
  •   Breadykid ·
    breadkid · 2018-10-08 13:23:37 +08:00 · 3799 次点击
    这是一个创建于 1998 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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