Interval Problems

IntervalCheck.java

/*
  Given a set of intervals, determine whether a number lies in any of those
  ranges.
  [1, 5], [7, 10]

  Example:
  5:  True
  11: False


  Given a set of intervals, determine the length of the range it covers
  i.e. the union

  Example:
  [1, 3], [2, 4], [2, 5]: 5
  [1, 5], [2, 3], [4, 5]: 5
  
  
  Given a set of intervals, determine the minimum number of points needed
  to ensure every interval has at least one point.
  
  Example:
  [1, 5], [2, 3], [4, 5]: 2
  
*/

import java.util.*;


class Interval implements Comparable<Interval>
{
  int start;
  int end;

  public Interval(int a, int b) {
    start = a;
    end = b;
  }

  public boolean inRange(int target) {
    return target >= start && target <= end;
  }

  public boolean isOverlap(Interval other) {
    return (start <= other.start && other.start <= end)
          || (start <= other.end && other.end <= end);
  }

  // Comparable function implementation
  public int compareTo(Interval i) {
    if(i.start == start) {
      return i.end - end;
    }
    return start - i.start;
  }
}

class IntervalCheck
{
  static Interval[] intvls;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    intvls = new Interval[num];

    for(int i = 0; i < num; i++) {
      intvls[i] = new Interval(sc.nextInt(), sc.nextInt());
    }

    int target = sc.nextInt();
    System.out.println(inIntervals(target));
    System.out.println(intervalsLength());
  }

  // Brute-force
  // Linear in the number of intervals with "constant storage"
  // (short of storing the input)
  public static boolean inIntervals(int target) {
    for(int i = 0; i < intvls.length; i++) {
      if(intvls[i].inRange(target)) {
        return true;
      }
    }
    return false;
  }

  // Sort based on start point
  // Linear in the number of intervals with constant storage
  public static int intervalsLength() {
    if(intvls.length == 0) {
      return 0;
    }

    Arrays.sort(intvls);

    int begin = intvls[0].start;
    int end = intvls[0].end;

    int len = intvls[0].end - intvls[0].start + 1;

    for(int i = 1; i < intvls.length; i++) {
      if(intvls[i].end <= end) {
        continue;
      } else if(begin <= intvls[i].start
                  && intvls[i].start <= end) {
        len += intvls[i].end - end;
        end = intvls[i].end;
      } else {
        len += intvls[i].end - intvls[i].start + 1;
        begin = intvls[i].start;
        end = intvls[i].end;
      }
    }

    return len;
  }

  public static int minPoints() {
    // If there's no overlap, easy decision
    // If there is, we have a decision to make
    //  Make a point
    //  and don't
    //  Use whichever is smaller
  }
}