Union of intervals

Posted on


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


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


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; 
        public int compareTo(Interval interval){
            if(this.left > interval.left){
              return 1; 
            }else if(this.left < interval.left){
              return -1;    
              return 0;
        public String toString(){
         return "("+this.left+","+this.right+")";

    public List<Interval> getUnion(List<Interval> 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>()

        for (IntervalUnion.Interval i:intervalUnion.getUnion(sample)){


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


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


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…


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)

Leave a Reply

Your email address will not be published. Required fields are marked *