Sunday, December 28, 2014

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.



import java.util.*;
public class FindRange {
 public int findRange (ArrayList 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 {
  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;
 }

}

No comments:

Post a Comment