java - 插入或删除到非重叠连续区间集合

Question

给定一组已排序的非重叠连续区间，如何添加新区间或从中删除现有区间。请建议我一个好的数据结构来存储这些间隔，这可以使这些更改成为可能。

例子:

Given collection: [1,4), [4,9), [9,12)

Insert: [5,8)
Result: [1,4), [4,5), [5, 8), [8, 9), [9, 12)

Delete: [4, 5)
Result: [1,5),  [5, 8), [8, 9), [9, 12)

在删除的情况下，如果可能的话，它应该首先添加到前一个，否则下一个。

Answer 1

我根本不会为离散间隔而烦恼。由于定义需要“排序的非重叠连续间隔”，我只存储间隔的边界(“intervalBoundaries”)，然后从该列表中，我将按需创建间隔范围(“getRanges()").

这里是我的例子(也许应该修改“deleteRange()”-方法以涵盖边缘情况):

/*
 */
package de.test.stackoverflow;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.lang.StringUtils;

public class Intervals {

    public static final class Range {

        final int from;
        final int to;

        public Range(int from, int to) {
            this.from = from;
            this.to = to;
        }

        public int getFrom() {
            return from;
        }

        public int getTo() {
            return to;
        }

        @Override
        public String toString() {
            return String.format("[%d, %d)", from, to);
        }

    }

    final SortedSet<Integer> intervalBoundaries = new java.util.TreeSet<>();

    public List<Range> getRanges() {
        final List<Range> res = new java.util.ArrayList<>();
        if (intervalBoundaries.size() > 1) {
            final List<Integer> tmpBounds = new java.util.ArrayList<>(intervalBoundaries);
            for (int i = 0; i < tmpBounds.size() - 1; i++) {
                res.add(new Range(tmpBounds.get(i), tmpBounds.get(i + 1)));
            }
        }
        return res;
    }

    public void insertBoundary(Integer bound) {
        // duplicates in sets are automatically removed
        intervalBoundaries.add(bound);
    }

    public void insertRange(Integer from, Integer to) {
        intervalBoundaries.add(from);
        intervalBoundaries.add(to);

    }

    public void insertRange(Range x) {
        insertRange(x.getFrom(), x.getTo());
    }

    public void deleteRange(Range x) {
        final Collection<Integer> boundsToDelete = new java.util.LinkedHashSet<>();
        for (Integer intervalBoundary : intervalBoundaries) {
            if (intervalBoundary >= x.getFrom() && intervalBoundary < x.getTo()) {
                boundsToDelete.add(intervalBoundary);
            }
        }
        intervalBoundaries.removeAll(boundsToDelete);
        if (x.getTo() < intervalBoundaries.last()) {
            insertBoundary(x.getTo());
        }
        if (x.getFrom() > intervalBoundaries.last()) {
            insertBoundary(x.getFrom());
        }
    }    

    public static void main(String[] args) {
        Intervals i = new Intervals();
        i.insertRange(new Range(1, 4));
        i.insertRange(new Range(4, 9));
        i.insertRange(new Range(9, 12));
        System.out.println("Given collection: " + StringUtils.join(i.getRanges(), ", "));
        final Range insertRange = new Range(5, 8);
        System.out.println("insert: " + insertRange);
        i.insertRange(insertRange);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
        final Range deleteRange = new Range(4, 5);
        System.out.println("delete: " + deleteRange);
        i.deleteRange(deleteRange);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
        final Range deleteRange2 = new Range(3, 9);
        System.out.println("delete: " + deleteRange2);
        i.deleteRange(deleteRange2);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
        final Range deleteRange3 = new Range(2, 15);
        System.out.println("delete: " + deleteRange3);
        i.deleteRange(deleteRange3);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));

    }

}