1

我有两组区间：一组包含介于 0 和 100 之间的“正”区间；另一个包含 -100 和 0 之间的“负”区间。每个集合中的区间不一定是唯一的（在这种情况下，“集合”可能比“集合”更好），并且可以重叠。例如，正集是

{ [0, 10], [5,15], [5,15], [10,15], [10,20], [25, 40] }

负集是

{ [-15, 0], [-15,-5], [-20,-15], [-30,-25] }

每组内相邻的非重叠区间（即，一个的右端点等于另一个的左端点的那些区间）可以组合形成更长的区间，例如[0,10] + [10 ,20] = [0,20] 和 [-15,0] + [-20,-15] = [-20,0]，但是 [0,10] 和 [5,15]不能组合成 [0 ] ,15]。

如果正负区间在绝对数上跨越完全相同的范围，例如 [5,15] + [-15,-5] = 0 和 [0,10] + [10,20]，则它们可以相互取消+ [-15,0] + [-20,-15] = [0,20] + [-20,0] = 0。

我正在寻找一种有效的算法，以最小化剩余间隔的总组合长度的方式加入和取消间隔。在示例中，剩余总长度 = len([5,15]) + len([10,15]) + len([25,40]) + len([-30,-25]) = 10 + 5 + 15 + 5 = 35。

也许这类问题已经在文献中的某个地方或这里得到解决（我找不到任何东西，但也许只是因为我不知道如何以正式的方式表述它），所以我将不胜感激参考和链接；或者这里发布的解决方案当然也足够了。

以下是我对可以采取的（非常）高级步骤的第一个天真的想法。这个想法是，左端点与某个负区间的左端点匹配的正区间是“潜在可取消的”，如果它的右端点与某个负区间的右端点匹配，或者如果其中之一它的相邻间隔是“潜在可取消的”。

让我们使用两个集合的正数来表示区间的左 ( l) 和右 ( r) 端点，称它们l+/l-和r+/r-表示正/负集合。设置S = 0。

  1. 找到所有左端点 满足l+ = l- = l和所有右端点 满足r+ = r- = r。对于每一个这样l和每一个r，找到n_l = min{number of positive intervals with l+ = l; number of negative intervals with l- = l}和n_r = min{number of positive intervals with r+ = r; number of negative intervals with r- = r}。

  2. l_min从匹配的左端点集合中找到最小的，并{l}从匹配的右端点集合中Step 1找到最大的。保留完全介于两者之间的所有间隔，以便在后续步骤中进行进一步处理。计算）。r_max{r}Step 1l_minr_maxS = S + (the total length of the intervals which do not fall entirely between the two bounds l_min and r_max

  3. 以升序按左端点对每个集合中的间隔进行排序。

  4. 在每个左端点，按其长度降序排列间隔。

  5. 从最左边的点 开始循环遍历所有正区间l_min。

  6. 将区间的右端点r与来自的匹配右端点集进行比较Step 2。

  7. 如果没有Step 6找到匹配项，则寻找下一个区间，其左端点等于当前区间的右端点。

  8. 如果找到区间 in Step 7，则使用它返回Step 6。

  9. 如果没有Step 7找到区间 in ，则将当前区间的长度添加到长度的总和中S。n_l将当前区间的左端点对应的减1 n_l := n_l - 1：。如果生成的新值n_l = 0则转到Step 2。如果n_l > 0然后转到Step 5并采用与当前间隔相同的左端点的下一个间隔。从进一步的步骤中删除当前间隔。

  10. 如果找到匹配Step 6项，则使用负间隔转到Step 5.

工作正在进行中...

[...]

  1. 对于每个集合（正 S+ 和负 S-），构建将非唯一区间视为相同的区间的最长可能组合。假设在加入 k+ = 1..N_C+ 和 k- = 1..N_C- 之后，可能有 N_C+ 和 N_C- 不同的组合，每个组合都包含 N_k+ 和 N_k- 区间。

  2. 比较两组之间的这些组合（从包含最长间隔的那些组合开始）消除/取消重合部分。

  3. 计算总剩余长度。

显然，上面有很多细节需要填写，但在这一点上，我什至不确定这种方法是否能保证找到最小解决方案。

4

0 回答 0