title: algorithm/complexity - most efficient way to solve
body: <p>So the question is this.  I have the following as an example input,</p>
  
  <p>|ID | A | B |</p>
  
  <p>|2  |100|200|</p>
  
  <p>|3  |110|190|</p>
  
  <p>|4  |105|145|</p>
  
  <p>|1  |90 |150|</p>
  
  <p>|5  |102|198|</p>
  
  <p>and the goal is the following.  For each ID x, compute the number of other IDs y where A of y is greater that A of x and B of y is less than B of x.  So the output of the above example should be</p>
  
  <p>|ID|count|</p>
  
  <p>|3 |0    |</p>
  
  <p>|4 |0    |</p>
  
  <p>|1 |1    |</p>
  
  <p>|5 |2    |</p>
  
  <p>|2 |3    |</p>
  
  <p>Where ID 3 has count 0 because it has the largest A. Obviously you could do O(n^2) exhaustive search but that would be inefficient.</p>
  
  <p>My algorithm is the following. Sort the input twice - once by A and once by B, getting</p>
  
  <p>|ID | A | B |    </p>
  
  <p>|1  |90 |150|</p>
  
  <p>|2  |100|200|</p>
  
  <p>|5  |102|198|</p>
  
  <p>|4  |105|145|</p>
  
  <p>|3  |110|190|</p>
  
  <p>and</p>
  
  <p>|ID | A | B |</p>
  
  <p>|2  |100|200|</p>
  
  <p>|5  |102|198|</p>
  
  <p>|3  |110|190|</p>
  
  <p>|1  |90 |150|</p>
  
  <p>|4  |105|145|</p>
  
  <p>Then start with the first ID in the first sorted table (ID=1) and get the ID's with a larger A value (i.e. the ID's below it - 2,5,4,3) then lookup ID=1 on the second sorted table and look at the ID's below it and everytime one is found in the original set of ID's a counter is incremented - in this case the only ID below 1 in the second table is 4 and 4 is in {2,5,4,3} so the output is 1.</p>
  
  <p>So sorting is O(nlogn) and I believe the rest of the operations are constant.  Is there a better method?</p>