我的平家小院
2016-12-22 01:18
采纳率: 0%
浏览 2.8k

算法:一个时间段a和多个不重叠时间段对比,得出a时间段中与其他时间段的不重叠时间段

目前开发中遇到一个问题,就是算法:一个时间段a和多个不重叠时间段对比,得出a时间段中与其他时间段的不重叠时间段,思路不是很清晰,就高手提点下

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

6条回答 默认 最新

  • Book1346 2016-12-22 01:43

    楼主的问题应该是求差集吧?
    对于楼主的问题,。我也不知道我理解得对不对。
    思路:
    因为除了A,其他都确定是不重叠的时间段了,所有你要求出A与其他时间段的不重叠时间段时,
    只要一个一个去比对就行了。而且一直用上一比对结果来比对下一比对结果。
    对于给予的不重叠时间段有N个,那么遍历这N个时间段,把A逐一与这N个时间段比对。
    每比对一次,都能得到一段新的不重叠的A时间段,然后再把这个新的A时间段拿去比对下一个要比对的时间段。
    比对结束后就是结果了。
    对于算法,可以先对N个时间段进行排序,然后你比对的时候可以采用二分法,可以优化很多时间。

    评论
    解决 无用
    打赏 举报
  • apples_kk 2016-12-22 01:56

    问题描述不清
    假如 a={4,9}
    其他时间段 b={1,2},c={3,5},d={5,6},e={3,12}

    1、按照你的描述不重叠时间段,最终的输出是:b={1,2}
    2、还是要做计算输出其他呢?

    评论
    解决 无用
    打赏 举报
  • Tiger_Zhao 2016-12-22 02:06

    1)我们先约定用a[B,E]方式表示时间段结构a,起始时间是a.B,结束时间是a.E。
    2)讨论取a[B,E]b1[B,E]不重叠部分:
    2.a)当 (a.E<=b1.B)||(b1.E<=a.B) 时,无重叠,保留原先的a
    2.b)否则有重叠,去掉原先的a;
    (a.B<b1.B)&&(b1.B<=a.E) 时,留下左边非重复段 a1[a.B,b1.B]
    (a.B<=b1.E)&&(b1.E<a.E) 时,留下右边非重复段 a2[b1.E,a.E]
    3)对上面留下的每个a,都按找2)的逻辑和下个b2去重叠。
    4)重复直到没有留下任何a或所有的b都用完了。

    评论
    解决 无用
    打赏 举报
  • miaoch 2016-12-22 02:28

    如果时间段 可能用 一些点的组合表示,那只要遍历其他时间段 去移除这些点 剩余的点就是解。
    如果是指一个区间比如[1,5] 其他的区间有 [0,2] [3,4] [5,6] 因为已知剩余区间也不会有重叠部分
    相当于就是求 a 和 剩余区间的差集, 那只要一个一个减过去就行了

    评论
    解决 无用
    打赏 举报
  • 天堂2013 2016-12-22 02:36

    假设时间区间用(A,B)表示,现在有另外一个时间区间(C,D),要判断(C,D)是否与(A,B)有重叠部分,则只需要满足:C的值大于B的值或者D的值小于A的值(注意中间用或运算符),就表示没有重叠部分

    评论
    解决 无用
    打赏 举报
  • liang_shui_guo 2016-12-22 06:17

    遍历所有时间段,一个一个对比,把重叠部分删除

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题