压缩间隔列表

Question

我需要将间隔列表压缩成较小的列表。让我解释一下：
例如，我有一个包含间隔 [1,4]、[2,5]、[5,7]、[10,11]、[13,20]、[19,21] 的列表，我想加入相交的intervals 和 return 列表 [1,7],[10,11],[13,21] 将相交的间隔转换为单个更长的间隔。
为此我写了这个方法：

public List compress(List<Interval> intervals) {

    for (int j = 0; j < intervals.size(); j++) {
        Interval a = intervals.get(j);
        int aIndex = j;

        for (int i = 1 + aIndex; i < intervals.size(); i++) {
            Interval b = intervals.get(i);

            if (a.intersects(b)) {
                //the union method return a union of two intervals. For example returns [1,7] for [1,4] and [2,5]
                intervals.add(j, a.union(b));
                intervals.remove(j+1);
                intervals.remove(i);
            }
        }
    }

    return intervals;
}

这对于检查的第一对间隔似乎工作正常，但它停在那里。即最终输出是一个包含 [1, 5],[5, 7],[10, 11],[13, 20],[19, 21].
的列表我发现这可能是从列表中非法删除元素的问题？ https://codereview.stackexchange.com/questions/64011/removing-elements-on-a-list-while-iterating-through-it?newreg=cc3f30e670e24cc2b05cd1fa2492906f 但我不知道如何解决这个问题。请任何人给我提示。

注意：抱歉，如果我做错了什么，因为这是我第一次 post 到 Whosebug。并感谢任何愿意提供帮助的人。

更新：这是我在 Maraboc 建议创建列表副本并操作该列表后找到的解决方案。这似乎有效。

public List compress(List<Interval> intervals) {

    List<Interval> man = intervals;
    for (int j = 0; j < intervals.size(); j++) {
        Interval a = intervals.get(j);
        int aIndex = j;

        for (int i = 1 + aIndex; i < intervals.size(); i++) {
            Interval b = intervals.get(i);

            if (a.intersects(b)) {
                a = a.union(b);
                man.add(j,a);
                man.remove(j+1);
                man.remove(i);
                i--;
            }
        }
    }

    return intervals;
}

谢谢大家

Answer 1

您实际上没有使用迭代器，您使用的是循环和 select 列表中基于位置的元素，因此您不必担心 "I am not able to remove while iterating" 问题。

Answer 2

要使您的算法正常工作，必须对间隔进行排序，例如按开始排序。

然后for-i循环可以使a成为可能的最长间隔。

       if (a.intersects(b)) {
            a = a.union(b);
            intervals.remove(i);
            --i; // So we remain at old i value.
        }
    } // for i
    intervals.set(j, a);

之所以有这些要求，是因为区间 A、B、C 可能形成一个长区间 ABC，而 C.B、A 可能。

Answer 3

问题确实在于，当您从列表中删除一个元素时，所有后续元素都将被移动。在 j 左右，我猜它不会改变，因为您在同一位置插入然后删除了一个项目。但是在位置 i 的删除将移动列表中的所有元素。

您可以做的不是删除元素，而是在该位置放置一个空值，以便索引保持不变。然后您将必须执行最后一次传递以从数组中删除空元素（并在比较之前检查空值）。

你也可以运行你的内部循环向后（从最大 i 向下到 j）这样任何在 i 之后移动的元素都已经被处理了.

Answer 4

我错把这个问题先发到stackexchange了。他们将我重定向到这个地方，问题被搁置了。但在那之前 Maraboc[a link](https://codereview.stackexchange.com/users/87685/maraboc ) 帮忙出个主意。他告诉我创建一个新列表并修改该列表。我这样做了，它似乎有效。更新的解决方案将在更新的问题中。

Answer 5

只是为了好玩，我采用了现有的 Interval Tree 并添加了一个似乎工作得很好的 minimise 方法。

/**
 * Title: IntervlTree
 *
 * Description: Implements a static Interval Tree. i.e. adding and removal are not possible.
 *
 * This implementation uses longs to bound the intervals but could just as easily use doubles or any other linear value.
 *
 * @author OldCurmudgeon
 * @version 1.0
 * @param <T> - The Intervals to work with.
 */
public class IntervalTree<T extends IntervalTree.Interval> {
    // My intervals.

    private final List<T> intervals;
    // My center value. All my intervals contain this center.
    private final long center;
    // My interval range.
    private final long lBound;
    private final long uBound;
    // My left tree. All intervals that end below my center.
    private final IntervalTree<T> left;
    // My right tree. All intervals that start above my center.
    private final IntervalTree<T> right;

    public IntervalTree(List<T> intervals) {
        if (intervals == null) {
            throw new NullPointerException();
        }

        // Initially, my root contains all intervals.
        this.intervals = intervals;

        // Find my center.
        center = findCenter();

        /*
         * Builds lefts out of all intervals that end below my center.
         * Builds rights out of all intervals that start above my center.
         * What remains contains all the intervals that contain my center.
         */
        // Lefts contains all intervals that end below my center point.
        final List<T> lefts = new ArrayList<>();
        // Rights contains all intervals that start above my center point.
        final List<T> rights = new ArrayList<>();

        long uB = Long.MIN_VALUE;
        long lB = Long.MAX_VALUE;
        for (T i : intervals) {
            long start = i.getStart();
            long end = i.getEnd();
            if (end < center) {
                lefts.add(i);
            } else if (start > center) {
                rights.add(i);
            } else {
                // One of mine.
                lB = Math.min(lB, start);
                uB = Math.max(uB, end);
            }
        }

        // Remove all those not mine.
        intervals.removeAll(lefts);
        intervals.removeAll(rights);
        uBound = uB;
        lBound = lB;

        // Build the subtrees.
        left = lefts.size() > 0 ? new IntervalTree<>(lefts) : null;
        right = rights.size() > 0 ? new IntervalTree<>(rights) : null;

        // Build my ascending and descending arrays.
        /**
         * @todo Build my ascending and descending arrays.
         */
    }

    /*
     * Returns a list of all intervals containing the point.
     */
    List<T> query(long point) {
        // Check my range.
        if (point >= lBound) {
            if (point <= uBound) {
                // Gather all intersecting ones.
                List<T> found = intervals
                        .stream()
                        .filter((i) -> (i.getStart() <= point && point <= i.getEnd()))
                        .collect(Collectors.toList());

                // Gather others.
                if (point < center && left != null) {
                    found.addAll(left.query(point));
                }
                if (point > center && right != null) {
                    found.addAll(right.query(point));
                }

                return found;
            } else {
                // To right.
                return right != null ? right.query(point) : Collections.<T>emptyList();
            }
        } else {
            // To left.
            return left != null ? left.query(point) : Collections.<T>emptyList();
        }

    }

    /**
     * Blends the two lists together.
     *
     * If the ends touch then make them one.
     *
     * @param a
     * @param b
     * @return
     */
    static List<Interval> blend(List<Interval> a, List<Interval> b) {
        // Either empty - lreturn the other.
        if (a.isEmpty()) {
            return b;
        }
        if (b.isEmpty()) {
            return a;
        }
        Interval aEnd = a.get(a.size() - 1);
        Interval bStart = b.get(0);
        ArrayList<Interval> blended = new ArrayList<>();
        // Do they meet?
        if (aEnd.getEnd() >= bStart.getStart() - 1) {
            // Yes! merge them.
            // Remove the last.
            blended.addAll(a.subList(0, a.size() - 1));
            // Add a combined one.
            blended.add(new SimpleInterval(aEnd.getStart(), bStart.getEnd()));
            // Add all but the first.
            blended.addAll(b.subList(1, b.size()));
        } else {
            // Just join them.
            blended.addAll(a);
            blended.addAll(b);
        }
        return blended;
    }

    static List<Interval> blend(List<Interval> a, List<Interval> b, List<Interval>... more) {
        List<Interval> blended = blend(a, b);
        for (List<Interval> l : more) {
            blended = blend(blended, l);
        }
        return blended;
    }

    List<Interval> minimise() {
        // Calculate min of left and right.
        List<Interval> minLeft = left != null ? left.minimise() : Collections.EMPTY_LIST;
        List<Interval> minRight = right != null ? right.minimise() : Collections.EMPTY_LIST;
        // My contribution.
        long meLeft = minLeft.isEmpty() ? lBound : Math.max(lBound, minLeft.get(minLeft.size() - 1).getEnd());
        long meRight = minRight.isEmpty() ? uBound : Math.min(uBound, minRight.get(0).getEnd());
        return blend(minLeft,
                Collections.singletonList(new SimpleInterval(meLeft, meRight)),
                minRight);
    }

    private long findCenter() {
        //return average();
        return median();
    }

    protected long median() {
        if (intervals.isEmpty()) {
            return 0;
        }
        // Choose the median of all centers. Could choose just ends etc or anything.
        long[] points = new long[intervals.size()];
        int x = 0;
        for (T i : intervals) {
            // Take the mid point.
            points[x++] = (i.getStart() + i.getEnd()) / 2;
        }
        Arrays.sort(points);
        return points[points.length / 2];
    }

    /*
     * What an interval looks like.
     */
    public interface Interval {

        public long getStart();

        public long getEnd();
    }

    /*
     * A simple implemementation of an interval.
     */
    public static class SimpleInterval implements Interval {

        private final long start;
        private final long end;

        public SimpleInterval(long start, long end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public long getStart() {
            return start;
        }

        @Override
        public long getEnd() {
            return end;
        }

        @Override
        public String toString() {
            return "{" + start + "," + end + "}";
        }
    }

    /**
     * Test code.
     *
     * @param args
     */
    public static void main(String[] args) {
        /**
         * @todo Needs MUCH more rigorous testing.
         */
        // Test data.
        long[][] data = {
            {1, 4}, {2, 5}, {5, 7}, {10, 11}, {13, 20}, {19, 21},};
        List<Interval> intervals = new ArrayList<>();
        for (long[] pair : data) {
            intervals.add(new SimpleInterval(pair[0], pair[1]));
        }
        // Build it.
        IntervalTree<Interval> test = new IntervalTree<>(intervals);

        // Check minimise.
        List<Interval> min = test.minimise();
        System.out.println("Minimise test: ---");
        System.out.println(min);
    }
}

压缩间隔列表

Compressing a list of intervals

java

iteration

linked-list