数值范围的相交(或合并)算法 [英] Algorithm for Intersection (or Merge) of Numerical Ranges

问题描述

比方说，我有一个这样的范围列表:

Let's say I have a list of ranges like this:

列表A)0到3、9到14

List A) 0 to 3, 9 to 14

列表B)1至4、6至7、14至16

List B) 1 to 4, 6 to 7, 14 to 16

列表C)15(即15到15)

List C) 15 (i.e., 15 to 15)

我想得到这些范围的合并列表，结果看起来像这样:

I'd like to get a merged list of these ranges where the result would look like this:

合并结果列表)0到4、6到7、9到16

Merged Result List) 0 to 4, 6 to 7, 9 to 16

(请注意，结果是列表A，B和C的合并/交叉/合并)

(notice that the result is a merging/intersection/union of Lists A, B, and C)

我确定有一个算法可以解决，但是不知道.有人遇到过这个吗?

I'm sure there's an algorithm for this, but have no idea. Has anyone come across this before?

(伪代码或VB会很棒)

(pseudocode, or VB, would be great)

添加视觉表示:

推荐答案

使数组/成对列表(Value, Flag = +1 for start or -1 for end of range)

将这些对按Value排序(如果打成平局，请使用Flag作为辅助键)

Sort these pairs by Value (use Flag as secondary key in case of tie)

制作Counter = 0

遍历排序数组，将Flag添加到Counter

Walk through sorted array, adding Flag to Counter

Counter变为非零时，合并范围开始.

When Counter becomes non-zero, merged range begins.

Counter变为零时，合并范围结束

When Counter becomes zero, merged range ends

P.S.如果要合并触摸"间隔-在Value相同的情况下进行排序时，请在比较器功能中考虑Flag-例如，在(14,-1)之前的(14;+1)

P.S. If you want to merge "touching" intervals - account for Flag in comparator function during sorting when Value is the same - for example, (14;+1) before (14,-1)

这篇关于数值范围的相交(或合并)算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！