从范围列表中查找重叠范围 [英] Finding overlapping Range from Range List

问题描述

这不是Java特定的问题，但是我必须用Java来实现，这就是为什么我用Java对其进行了标记.

This is not a Java specific question, but I have to implement it in Java, that is why I tagged it with Java.

问题:

我有一个范围列表(在此示例中，由Stratpoint和Endpoint指定范围，我简单地使用int []):

I have a List of Ranges (a Range is specified by a Stratpoint and an Endpoint in this example i simple use an int[]):

在Java中:

List<int[2]> ranges = new ArrayList<>();
ranges.add(new int[]{1,100});
ranges.add(new int[]{30,95});
ranges.add(new int[]{10,60});
ranges.add(new int[]{15,25});
ranges.add(new int[]{33,66});
ranges.add(new int[]{20,50});
ranges.add(new int[]{51,100});
ranges.add(new int[]{25,70});

输出应该是一个范围，在大多数范围中都存在.在这种情况下，输出为 [33,50] .因为此范围在列表的6个范围之内.

The output should be a Range, that is present in the most Ranges. In this chase the output would be [33,50]. Because this Range is inside of 6 Ranges from the List.

希望您会理解我的问题.谢谢！

Hope you will understand my question. Thanks!

推荐答案

编辑:实际上，请参见

EDIT: Actually, just see this answer by @Dave, which is much more efficient.

编辑:不幸的是，我之前的代码有缺陷.例如，使用以下输入，它将输出范围99-100，而不是3-50.在此处尝试新代码.

EDIT: Unfortunately, my previous code is flawed. For example, with the below input, it outputs the range 99-100 instead of 3-50. Try the new code here.

Range(1, 100), Range(99, 100), Range(2, 50), Range(3, 90)

---

我写了另一种算法，但是这种算法速度较慢并且占用更多空间(时间和空间复杂度均为2 ^ n)

---

I wrote another algorithm, but this one is way slower and takes up more space (both time and space complexity are 2^n)

• 制作一个名为 rangeMap 的地图，其中的键是范围，值是该范围属于( Integers )
的其他范围.
• 对于范围列表中的每个范围 range :
  • 创建另一个地图 createdRanges ，再次将范围映射到整数
  • 对于 rangeMap 中的每个条目
    • 将 range2 和 n 定义为条目所保持的范围和整数
    • 如果 range 和 range2 重叠:
      • 将 newRange 定义为该重叠部分
      • 将 newN 定义为 n +1 ，因此我们知道该范围覆盖了另一个范围
      • 将 newRange 添加到 createdRanges 中，其值为 n + 1 .
      • Make a map called rangeMap where the keys are ranges and the values are how many other ranges that range is part of (Integers)
      • For every range range in your list of ranges:
        • Create another map createdRanges, again mapping ranges to integers
        • For every entry in rangeMap
          • Define range2 and n to be the range and integer that entry holds
          • If range and range2 overlap:
            • Define newRange to be that overlapping part
            • Define newN to be n + 1, so we know that another range was overlapped by this one
            • Add newRange to createdRanges, with the value n + 1.
            • 如果 rangeMap 中尚不存在该范围，请添加该范围以及相应的数字，该数字说明该范围重叠了多少个范围.
            • 否则，请检查地图中已存在的值是否小于此当前范围重叠的范围数.如果是这样，请更新该值.
            • If that range doesn't already exist in rangeMap, add that range and the corresponding number that says how many ranges it overlaps.
            • Otherwise, check if the value that is already in the map is less than the number of ranges this current range overlaps. If so, update that value.

            虽然这是非常低效的，但是如果您打算将其用于大量范围，则可以通过删除存在重叠(或相同数量)的范围较大的范围来优化它，以减少损坏限制较少，或以某种方式延迟了范围的计算等.

            While this is extremely inefficient, if you're going to use it for a large number of ranges, you can optimize it to be less bad by removing ranges for which there exist ranges with more overlaps (or the same number) and are less restrictive, or somehow delaying calculation of ranges, etc.

            链接至repl.it

            这篇关于从范围列表中查找重叠范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！