Thursday, May 28, 2015

L Question: Find Interval Range

public class Point implements Comparable<Point>{
 int x;
 int y;

 public Point() {
  this(0, 0);
 }

 public Point(int x, int y) {
  this.x = x;
  this.y = y;
 }

 @Override
 public int compareTo(Point other) {
  if (this.y == other.y) return 0;
  return this.y < other.y ? -1 : 1;
 } 
}

public int findRangeOfIntervals(Point[] points) {
  List<Point> list = Arrays.asList(points);
  Collections.sort(list);
  int lowerBound = -1;
  int upperBound = -1;
  int result = 0;

  for (int i = 0; i < list.size(); i++) {
   Point p = list.get(i);
   if (p.x <= upperBound) {
    if (p.y > upperBound) {
     upperBound = p.y;
    }
   } else {
    lowerBound = p.x;
    upperBound = p.y;
   }

   if (result < upperBound - lowerBound) {
    result = upperBound - lowerBound;
   }
  }

  return result;
 }

No comments:

Post a Comment