5
\$\begingroup\$

I am trying to solve for the problem with a bunch of intervals:

(1,2),(2,5),(4,7),(9,11)

I find their union, which in the above given case would be:

(1,7),(9,11)

It will be great to get some feedback on whether I am on the right track and how I can improve upon what I have.

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class IntervalUnion{
    class Interval implements Comparable<Interval>{
        private final int left;
        private final int right;
        Interval(int left,int right){
            this.left = left;
            this.right = right;
        }
        public int getRight(){
          return this.right;
        }
        public int getLeft(){
          return this.left; 
        }
        @Override
        public int compareTo(Interval interval){
            if(this.left > interval.left){
              return 1; 
            }else if(this.left < interval.left){
              return -1;    
            }else{
              return 0;
            }
        }
        @Override
        public String toString(){
         return "("+this.left+","+this.right+")";
        }
    }   

    public List<Interval> getUnion(List<Interval> intervals){
        Collections.sort(intervals);
        List<Interval> union = new ArrayList<Interval>();
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        for(Interval i:intervals){
            int currentRight = i.getRight();
            int currentLeft = i.getLeft();
            if(currentLeft <= right && currentRight > right){
              right = currentRight;
            }
            if(currentLeft < left && currentRight >= right){
              left = currentLeft;
              right = currentRight; 
            }
            if(currentLeft > right){
              union.add(new Interval(left,right));
              left = currentLeft;
              right = currentRight;
            }
        }
        union.add(new Interval(left,right));
        return union;
    }
    public static void main(String[] args){
      System.out.println("Testing out the union");
      IntervalUnion intervalUnion = new IntervalUnion();  
      IntervalUnion.Interval i1 = intervalUnion.new Interval(2,4);
      IntervalUnion.Interval i2 = intervalUnion.new Interval(1,1);
      IntervalUnion.Interval i3 = intervalUnion.new Interval(3,4);
      IntervalUnion.Interval i4 = intervalUnion.new Interval(0,3);
      IntervalUnion.Interval i5 = intervalUnion.new Interval(8,11);
      IntervalUnion.Interval i6 = intervalUnion.new Interval(7,8);
      IntervalUnion.Interval i7 = intervalUnion.new Interval(5,7);
      IntervalUnion.Interval i8 = intervalUnion.new Interval(9,11);
      IntervalUnion.Interval i9 = intervalUnion.new Interval(13,13);
      IntervalUnion.Interval i10 = intervalUnion.new Interval(16,17);
      IntervalUnion.Interval i11 = intervalUnion.new Interval(12,15);
      IntervalUnion.Interval i12 = intervalUnion.new Interval(12,14);

      List<IntervalUnion.Interval> sample = new ArrayList<IntervalUnion.Interval>()
                    {{
                      add(i1);
                      add(i2);
                      add(i3);
                      add(i4);
                      add(i5);
                      add(i6);
                      add(i7);
                      add(i8);
                      add(i9);
                      add(i10);
                      add(i11);
                      add(i12); 
                    }};

        for (IntervalUnion.Interval i:intervalUnion.getUnion(sample)){
        System.out.println(i);
    }
 }
}
\$\endgroup\$
1
  • \$\begingroup\$ Your solution relies on a sort so it has time complexity O(nlogn). If you are dealing with a particularly large number of intervals you should look into line sweep, which can give you O(n) complexity. \$\endgroup\$
    – mleyfman
    Mar 26 '15 at 15:30
5
\$\begingroup\$

No comments about the logic (yet?), but I do have something else to comment...

Validation

You should validate that the left field is never greater than the right field during instantiation, since your comparison logic makes use of that.

Endpoints

Slightly pernickety on this, but since your intervals includes both endpoints, your toString() representation should be using square braces instead of parentheses... See here for more info.

static classes?

If you make Interval a static class, you can 'freely' create instances without bounding to an instance of IntervalUnion. This really depends on your use case...

Comparisons

Your compareTo(Interval) code can be replaced by Integer.compareTo(int, int).

Creating Lists

Using Arrays.asList() is probably what you want, instead of the double-brace initialization...

Proper unit testing, please

Just displaying the output is not a unit test, you should assert that the output of calling intervalUnion.getUnion(sample) matches an expected Collection of Interval objects. For more info: Unit testing = Arrange, Act and Assert (link to another good CR answer).

What's good

I like that your Interval class is immutable.

Other suggestions

I wonder if this is a good case for Stream reduction operations...

edit: I now have my own take on your question/approach here, using stream reduction:

Onion Run Festival (or the unexpected anagram for Union of Intervals)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.