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

我有一个java范围实现为一个分为子范围的类。实现大致如下：如何计算出没有子范围相互重叠，并且所有子范围覆盖了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

什么是实现这一目标的最佳方式是什么？

编辑：

感兴趣的人在执行：

在我的验证码我做这些步骤：

转换有序映射到一个数组
强制第一和涵盖总范围的开始和结束的最后一个元素
迭代阵列元素并修复它们之间的间隙或重叠

守则第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; 
    } 
}

来源

2010-10-02 avee

Avee，请问您可以发布您的代码吗？我必须执行类似的验证，我不能拿出一些东西。在此先感谢。 – apatel 2010-10-15 19:11:06

嗨艾米特，这是我结束了： – avee 2010-10-17 14:29:51

嗨，我已经更新了我的问题，包括我的实施的一个片段，我希望它可以帮助 – avee 2010-10-17 15:12:06

由于您的subRange地图进行排序，您可以通过它进行迭代，并检查存在的end序列中下一个start没有间隙。当然，从您的总起点到第一个start和您最后的end到您的总终点。递归地应用此检查到所有subRange s。

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

来源

2010-10-02 09:08:49 tangens

这解决了这个问题，谢谢一堆！除了检查差距之外，我还会在每次迭代中检查重叠的子范围。 – avee 2010-10-02 11:36:33

另一种方法是完成所有范围的总和，并将其与所有范围内的最大值和最小值的差值进行比较。如果总和大于或等于三角洲，这意味着有交集。

来源

2012-10-09 14:28:26 user1732055

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

回答

相关问题