java - 如何计算没有子范围相互重叠并且所有子范围覆盖java中的整个范围？

Question

我在 java 中有一个范围实现为一个分为子范围的类。实现大致如下:

public class Range
{
   static public class Key implements Comparable<Key>
   {
      public int start;
      public int end;
      ...
   }

   Key range;
   SortedMap<Key, Range> subRange;
}

我想做一个函数来确保没有子范围相互重叠并且子范围的组合范围完全覆盖总范围。每个范围的开始和结束可以相等。

有效对象的示例:

Range: start 1, end 10
  subrange 1: start 1, end 2
  subrange 2: start 3, end 9
  subrange 3: start 10, end 10

实现这个的最佳方法是什么？

编辑:

任何对实现感兴趣的人:

在我的验证代码中，我执行以下步骤:

1. 将排序后的映射转换为数组
2. 强制第一个和最后一个元素覆盖总范围的开始和结束
3. 迭代数组元素并修复它们之间的间隙或重叠

第三步的代码:

for (int i=0; i < (rangeArray.length - 1); i++)
{
    if (rangeArray[i].range.end < (rangeArray[i+1].range.start - 1) ||
        rangeArray[i].range.end >= rangeArray[i+1].range.start)
    {
        // Alternatively, lose the if and just force subrange to behave this way
        rangeArray[i].range.end = rangeArray[i+1].range.start - 1; 
    }
}

Answer 1

由于您的 subRange map 已排序，您可以对其进行迭代并检查 end 的序列中是否没有间隙到下一个start .当然还有从你的总起点到第一个 start和你最后一个end到你的总终点。递归地将此检查应用于所有 subRange s也是。

为此，您的 map 必须按 start 排序，在您的示例中就是这种情况。