# Union of intervals

Posted on

Problem

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);
}
}
}
``````

Solution

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 `List`s

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)