重叠不止一次的区间的最大长度子集

Question

我已经为此困惑了一段时间，最后决定看看是否有人能想到一个有效的实现（我不确定是否有）。

给定一系列间隔（例如，以下）：

重叠多次的区间的最大子集是多少？在这种情况下，答案将是 [B, C, D]，因为 [A, B, C, D] 仅重叠一次，而其他重复重叠的子区间小于 3 个元素。

编辑 9/28：这是一个更复杂的例子：

在这种情况下，答案是 [B, D, E, F, H]，因为有多个点从左到右遍历此 table，其中此子集重叠。

另请注意，在这种情况下，答案将是 [A, B, C]。

Answer 1

在每组 n 个间隔的 O(n log n) 中，您可以获得所有相交的子集（参见 Find the maximally intersecting subset of ranges 并添加所需的簿记）。请注意，其中大约有 2n 个，其中 n 是集合中的点数（如果间隔共享起点或终点，则更少）。

我们可以将考虑限制在每组由一个区间相加形成的n组重叠点。这让我们从 2n 下降到 n。我们还可以将我们的考虑限制在元素被删除之前的集合。这可能会进一步减少集合的数量，但不能保证这样做。

现在我们需要找到具有最大交集的那对集合。

天真地这是 O(n^2)。

示例：将此应用于 OP 的示例，我们用以下间隔集结束此答案的第 2 段（使用第二段中的缩减）：

I: {{A,B}, {B,C,D}}
II: {{B,A,C,D}}

然后，我们找到 I 的集合与 II 的集合的最大交集：{B,C,D}

Answer 2

下面是我在 Java 中实现的解决方案。这类似于 Dave 的方法 sweep line algorithm.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class IntervalSolver {

     public static void main(String []args){
        ArrayList<Interval> intervals = new ArrayList<>();
        
        final int A = 0;
        final int B = 1;
        final int C = 2;
        final int D = 3;
        
//        intervals.add(new Interval(1, 10, A));
//        intervals.add(new Interval(9, 12, B));
//        intervals.add(new Interval(11, 15, C));
//        intervals.add(new Interval(11, 18, D));
//        intervals.add(new Interval(26, 29, A));
//        intervals.add(new Interval(20, 30, B));
//        intervals.add(new Interval(28, 33, C));
//        intervals.add(new Interval(27, 33, D));
        
//        intervals.add(new Interval(1, 10, A));
//        intervals.add(new Interval(1, 10, B));
//        intervals.add(new Interval(1, 10, C));
//        intervals.add(new Interval(1, 10, D));
//        intervals.add(new Interval(16, 25, A));
//        intervals.add(new Interval(16, 25, B));
//        intervals.add(new Interval(16, 25, C));
        
        intervals.add(new Interval(1, 7, A));
        intervals.add(new Interval(1, 10, B));
        intervals.add(new Interval(1, 10, C));
        intervals.add(new Interval(1, 10, D));
        
        compute(intervals, 4);
     }
     
     public static class Interval {
         public int start;
         public int end;
         public int entity;
         
         public Interval(int start, int end, int entity) {
             this.start = start;
             this.end = end;
             this.entity = entity;
         }
     }
     
     public static class Point implements Comparable<Point> {
         boolean start;
         public Interval interval;
         
         public int pos() {
             return start ? interval.start : interval.end;
         }
         
         public Point(Interval interval, boolean start) {
             this.interval = interval;
             this.start = start;
         }
         
         @Override
         public int compareTo(Point other) {
             int diff = pos() - other.pos();
             if (diff != 0)
                return diff;
             return (start ? 0 : 1) - (other.start ? 0 : 1);
         }
     }
     
     public static class Solution {
         public Interval[] intervals;
         
         public Solution(Interval[] intervals) {
             this.intervals = intervals;
         }
         
         public int value() {
             int value = 0;
             for (int i = 0; i < intervals.length; i++)
                 value += intervals[i] != null ? 1 : 0;
             return value;
         }
         
         @Override
         public boolean equals(Object other) {
             Solution s = (Solution)other;
             if (s.intervals.length != intervals.length)
                 return false;
             
             for (int i = 0; i < intervals.length; i++)
                 if ((intervals[i] == null && s.intervals[i] != null) || (intervals[i] != null && s.intervals[i] == null))
                     return false;
             return true;
         }
         
         @Override
         public int hashCode() {
             int hashCode = 0;
             for (int i = 0; i < intervals.length; i++)
                 hashCode = hashCode << 1 | (intervals[i] != null ? 1 : 0); 
             return hashCode;
         }
         
         @Override
         public String toString() {
             var sb = new StringBuilder();
             sb.append('[');
             for (int i = 0; i < intervals.length; i++) {
                 sb.append(intervals[i] != null ? '1' : '0');
                 if (i < intervals.length - 1)
                     sb.append(',');
             }
             sb.append(']');
             return sb.toString();
         }
     }
     
     public static void compute(List<Interval> series, int entities) {
         ArrayList<Point> points = new ArrayList<>();
         for (var i : series) {
             points.add(new Point(i, true));
             points.add(new Point(i, false));
         }
         points.sort(null);
         
         HashMap<Solution, Integer> solutions = new HashMap<>();
         Interval[] currentIntervals = new Interval[entities];
         
         for (int i = 0; i < points.size(); i++) {
             var p = points.get(i);
             
             if (p.start)
                 currentIntervals[p.interval.entity] = p.interval;
             else
                 currentIntervals[p.interval.entity] = null;
             
             if (i < points.size() - 1 && p.pos() == points.get(i + 1).pos())
                 continue;
             
             var copy = new Solution(currentIntervals.clone());
             int count = solutions.getOrDefault(copy, 0);
             solutions.put(copy, count + 1);
         }
         
         long maxValue = 0;
         Solution best = null;
         for (var entry : solutions.entrySet()) {
             var solution = entry.getKey();
             var count = entry.getValue();
             
             if (count == 1)
                 continue;
             
             long value = solution.value();
             if (value > maxValue) {
                 maxValue = value;
                 best = solution;
             }
         }
         
         // extra intersections:
         for (var entry : solutions.entrySet()) {
             var solution = entry.getKey();
             var count = entry.getValue();
             
             if (count > 1)
                 continue;
             
             long value = solution.value();
             if (value <= maxValue)
                 continue;
             
             for (var innerEntry : solutions.entrySet()) {
                 var innerSolution = innerEntry.getKey();
                 var innerCount = innerEntry.getValue();
                 
                 if (solution == innerSolution || innerCount > 1)
                     continue;
                 
                 long innerValue = innerSolution.value();
                 if (innerValue <= maxValue)
                     continue;
                 
                 var merge = new Solution(solution.intervals.clone());
                 for (int i = 0; i < entities; i++) {
                     var int1 = solution.intervals[i];
                     var int2 = innerSolution.intervals[i];
                     if (int2 == null || int1 == int2)
                         merge.intervals[i] = null;
                 }
                 
                 long mergeValue = merge.value();
                 if (mergeValue > maxValue) {
                     maxValue = mergeValue;
                     best = merge;
                 }
             }
         }         
         
         System.out.println("Best: " + best);
     }
}

它打印出 Best: [false, true, true, true] 表示 BCD。

它可以很容易地扩展以打印交叉点所在的精确坐标。

它的复杂度是 O(n*lg n + nk)，其中 n 是间隔数，k 是实体数。如果k = O(n)，那么整个复杂度就变成了O(n^2).

编辑： 更改了行为以说明 OP 要求中的更新。这个想法基于采用每对只出现一次的潜在解决方案并将它们相交。根据定义，它们的交集至少出现两次。如果它的值大于当前最好的，它就成为新的结果。复杂度已上升到 O(n*lg n + n^2*k)，其中 n 是间隔数，k 是实体数。如果k = O(n)，那么整个复杂度就变成了O(n^3).

编辑2： 通过添加同一实体的间隔必须不同的要求，修复了额外交叉点的代码。

重叠不止一次的区间的最大长度子集

Max length subset of intervals which overlaps more than once

algorithm

subset

intervals