数值范围相交(或合并)的算法
Algorithm for Intersection (or Merge) of Numerical Ranges
假设我有一个这样的范围列表:
列表 A) 0 到 3、9 到 14
列表 B) 1 到 4、6 到 7、14 到 16
列表 C) 15(即 15 到 15)
我想要获得这些范围的合并列表,结果如下所示:
合并结果列表)0 到 4、6 到 7、9 到 16
(注意结果是列表 A、B 和 C 的 merging/intersection/union)
我确定有一个算法可以解决这个问题,但我不知道。有人遇到过这个吗?
(伪代码,或 VB,会很棒)
添加视觉表示:
制作 array/list 对 (Value, Flag = +1 for start or -1 for end of range)
按 Value
对这些对进行排序(如果出现平局,则使用 Flag
作为辅助键)
制作Counter = 0
遍历排序数组,将 Flag
添加到 Counter
当Counter
变为非零时,合并范围开始。
当Counter
变为零时,合并范围结束
P.S。如果要合并 "touching" 间隔 - 在 Value
相同时在排序期间在比较器函数中考虑 Flag
- 例如,(14;+1)
在 (14,-1)
[= 之前22=]
假设我有一个这样的范围列表:
列表 A) 0 到 3、9 到 14
列表 B) 1 到 4、6 到 7、14 到 16
列表 C) 15(即 15 到 15)
我想要获得这些范围的合并列表,结果如下所示:
合并结果列表)0 到 4、6 到 7、9 到 16
(注意结果是列表 A、B 和 C 的 merging/intersection/union)
我确定有一个算法可以解决这个问题,但我不知道。有人遇到过这个吗?
(伪代码,或 VB,会很棒)
添加视觉表示:
制作 array/list 对 (Value, Flag = +1 for start or -1 for end of range)
按 Value
对这些对进行排序(如果出现平局,则使用 Flag
作为辅助键)
制作Counter = 0
遍历排序数组,将 Flag
添加到 Counter
当Counter
变为非零时,合并范围开始。
当Counter
变为零时,合并范围结束
P.S。如果要合并 "touching" 间隔 - 在 Value
相同时在排序期间在比较器函数中考虑 Flag
- 例如,(14;+1)
在 (14,-1)
[= 之前22=]