# Union of intervals

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){
left = currentLeft;
right = currentRight;
}
}
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)){
System.out.println(i);
}
}
}

• 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. Mar 26 '15 at 15:30

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...

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)