The Fake Geek's blog: Find Range

The Fake Geek's blog: Find Range
Given a list of tuples representing intervals, return the range these intervals 
covered. 
e.g: 
[(1,3), (2,5),(8,9)] should return 5
Click here for original question.
I am not a big fan to use fancy containers for problems like this. To me, the primary goal is to reduce time complexity to <= O(n) if possible and maintain constant space complexity. The only reason to use containers is to reduce the time complexity, which is at the expense of space complexity.

Here is an O(n) solution with nothing, just a single loop.

public class FindRange {

 public int findRange (ArrayList<interval> intervals) {

  if (intervals == null)

   throw new NullPointerException();

  if (intervals.size() == 0)

   return 0;

  Collections.sort(intervals, new IntervalComparator());

  int min_start = intervals.get(0).start;

  int max_end = intervals.get(0).end;

  int range = 0;

  int index = 1;

  while (index <= intervals.size()) {

   if (index == intervals.size()) {

    range += (max_end - min_start);

    break;

   }

   if (intervals.get(index).start <= max_end) {

    max_end = Math.max(max_end, intervals.get(index).end);

    index++;

    continue;

   }

   range += (max_end - min_start);

   min_start = intervals.get(index).start;

   max_end = intervals.get(index).end;

   //index++;

  }

  return range;

   

 }

  

 private class IntervalComparator implements Comparator<interval> {

  public int compare(Interval a, Interval b) {

   return a.start - b.start;

  }

 }

}

public class Interval {

  int start;

  int end;

 public Interval() {

  this.start = Integer.MIN_VALUE;

  this.end = Integer.MAX_VALUE;

 }

 public Interval(int start, int end) {

  this.start = start;

  this.end = end;

  if (!isValid())

   throw new IllegalArgumentException("invalid input!");

 }

 private boolean isValid() {

  return start <= end;

 }

}

http://www.careercup.com/question?id=4695029784248320

public static int findRange(ArrayList<Interval> intervals) {
  Collections.sort(intervals, new Comparator<Interval>() {
   @Override
   public int compare(Interval o1, Interval o2) {
    if (o1.start > o2.start) {
     return 1;
    } else if (o1.start > o2.start) {
     return -1;
    } else if (o1.end > o2.end){
     return 1;
    } else if (o1.end > o2.end) {
     return -1;
    } else {
     return 0;
    }
   }
  });
  
  int range = 0;
  int s = 0;
  int i = 0;
  while (i < intervals.size()) {
   int j = i + 1;
   int e = intervals.get(i).end;
   while (j < intervals.size() && e >= intervals.get(j).start) {
    e = Math.max(e, intervals.get(j).end);
    j++;
    
   }
   range += e - intervals.get(s).start;
   i = j;
   s = j;
  }
  return range;
 }

Read full article from The Fake Geek's blog: Find Range