Interval set in java

I have a list of intervals with integer values ​​[e.g. [1, 4], [10, 19], etc.]. Is there a way to put these intervals in a java collection container [e.g. Set] so that I can call the union function on the container. The union function should give me a list of intervals, so if any 2 inserted intervals overlap, they should be combined into output. I tried using the Range class in Guava, but ended up comparing all the intervals with each other before merging. The elegant approach to this will be truly appreciated! Here is what I tried based on the answer below. The conclusion is [[1, 15], [17, 20]], which is correct. I wanted to know if there is any API that implements something like this.

public static void main(String[] args) {
    // mock data
    List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>();
    rng_lst.add(new MyIntRange(1, 10));
    rng_lst.add(new MyIntRange(5, 15));
    rng_lst.add(new MyIntRange(17, 20));

    // sort intervals by start position
    Collections.sort(rng_lst);

    // merge the intervals which overlap
    List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>();
    MyIntRange old_rng = null;
    for (MyIntRange cur_rng : rng_lst) {
        if (old_rng == null) {
            old_rng = cur_rng;
        } else {
            if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) {
                // this does not over lap with the next one
                res_lst.add(old_rng);
                old_rng = cur_rng;
            } else {
                // overlap
                old_rng = new MyIntRange(old_rng.rng.lowerEndpoint(),
                        cur_rng.rng.upperEndpoint());
            }
        }
    }
    // add the last range
    res_lst.add(old_rng);

    // done!
    System.out.println(res_lst);
}

// wrapper around Guava Range to make it comparable based on the
// interval start
public static class MyIntRange implements Comparable<MyIntRange> {
    Range<Integer> rng;

    public MyIntRange(int start, int end) {
        rng = Ranges.closed(start, end);
    }

    public int compareTo(MyIntRange that) {
        int res = -1;
        if (this.rng.lowerEndpoint() > that.rng.lowerEndpoint()) {
            res = 1;
        }
        return res;
    }

    public String toString() {
        return "[" + rng.lowerEndpoint() + ", " + rng.upperEndpoint() + "]";
    }
}

thank

+5
2

, RangeSet Guava 14.0, , , , .

+5

:

  • start
  • . i th:
    • i (i+1) st.
    • , i i+1 i+1. ( .)

: O(nlgn), - . ( , .)

+2

All Articles