title: Given a set of intervals, find how many intervals contain a point
body: <p>Suppose you are given a set of N intervals (represented as left and right coordinates) and M points. For each point P algorithm should find number of intervals to which P belongs.</p>
  
  <p>Here's my algorithm:</p>
  
  <p>1) Put left and right coordinates of intervals in "left" and "right" arrays respectively</p>
  
  <p>2) Sort "left", exchanging entries simultaneously with "right"</p>
  
  <p>3) Given a point P, find a maximum i such that left[i] &lt;= P</p>
  
  <p>4) For each j &lt;= i, add 1 to result if right[j] >= P</p>
  
  <p>5) Return result</p>
  
  <p>Implementation in Java:</p>
  
  <pre><code>import java.util.*;
  
  class Intervals {
  
      public  static int count(int[] left, int[] right, int point) {
          int k = find(left, point), result = 0;
          for (int i=0; i &lt; k; i++)
              if (point &lt;= right[i]) result++;
          return result;
      }
  
  
      private static int find(int[] a, int point) {
          if (point &lt; a[0]) return -1;
          int i = 0;
          while (i &lt; a.length &amp;&amp; a[i] &lt;= point) i++;
          return i;
      }
  
      private static void sort(int[] a, int[] b) {
          sort(a, b, 0, a.length-1);
      }
  
      private static void sort(int[] left, int[] right, int lo, int hi) {
          if (hi &lt;= lo) return;
          int lt = lo, gt = hi;
          exchange(left, right, lo, lo + (int) (Math.random() * (hi-lo+1)));
          int v = left[lo];
          int i = lo;
          while (i &lt;= gt) {
              if      (left[i] &lt; v) exchange(left, right, lt++, i++);
              else if (left[i] &gt; v) exchange(left, right, i, gt--);
              else                  i++;
          }
          sort(left, right, lo, lt-1);
          sort(left, right, gt+1, hi);
      }
  
      private static void exchange(int[] left, int[] right, int i, int j) {
          int temp  = left[i];
          left[i]   = left[j];
          left[j]   = temp;
          temp      = right[i];
          right[i]  = right[j];
          right[j]  = temp;
      }
  
      private static boolean less(int[] a, int i, int j) {
          return a[i] &lt; a[j];
      }
  
  
      public static void main(String[] args) {
          int n       = Integer.parseInt(args[0]);
          int m       = Integer.parseInt(args[1]);
          int[] left  = new int[n];
          int[] right = new int[n];
          Random r    = new Random();
          int MAX     = 100000;
          for (int i = 0; i &lt; n; i++) {
              left[i] = r.nextInt(MAX);
              right[i] = left[i] + r.nextInt(MAX/4);
          }
          sort(left, right);
          for (int i=0; i &lt; m; i++)
              System.out.println(count(left, right, r.nextInt(MAX)));
      }
  }
  </code></pre>
  
  <p>This code has not passed some test, and I'm trying to find a bug. Point is that I actually don't know what input data used in these tests.</p>
  
  <p>Thanks.</p>