目前开发中遇到一个问题,就是算法:一个时间段a和多个不重叠时间段对比,得出a时间段中与其他时间段的不重叠时间段,思路不是很清晰,就高手提点下
楼主的问题应该是求差集吧?
对于楼主的问题,。我也不知道我理解得对不对。
思路:
因为除了A,其他都确定是不重叠的时间段了,所有你要求出A与其他时间段的不重叠时间段时,
只要一个一个去比对就行了。而且一直用上一比对结果来比对下一比对结果。
对于给予的不重叠时间段有N个,那么遍历这N个时间段,把A逐一与这N个时间段比对。
每比对一次,都能得到一段新的不重叠的A时间段,然后再把这个新的A时间段拿去比对下一个要比对的时间段。
比对结束后就是结果了。
对于算法,可以先对N个时间段进行排序,然后你比对的时候可以采用二分法,可以优化很多时间。
问题描述不清
假如 a={4,9}
其他时间段 b={1,2},c={3,5},d={5,6},e={3,12}
1、按照你的描述不重叠时间段,最终的输出是:b={1,2}
2、还是要做计算输出其他呢?
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都用完了。
如果时间段 可能用 一些点的组合表示,那只要遍历其他时间段 去移除这些点 剩余的点就是解。
如果是指一个区间比如[1,5] 其他的区间有 [0,2] [3,4] [5,6] 因为已知剩余区间也不会有重叠部分
相当于就是求 a 和 剩余区间的差集, 那只要一个一个减过去就行了
假设时间区间用(A,B)表示,现在有另外一个时间区间(C,D),要判断(C,D)是否与(A,B)有重叠部分,则只需要满足:C的值大于B的值或者D的值小于A的值(注意中间用或运算符),就表示没有重叠部分
遍历所有时间段,一个一个对比,把重叠部分删除