title: Finding the most frequent number from a set of ranges -
body: <p>The question is as follows:-</p>
  
  <p>You are given the life time of N different elephants, represented as a pair of integers.</p>
  
  <p>ex. [5,10] [6,15] [2,7]
  means, one elephant lived from Year 5 to Year 10. The second lived from Year 6 to Year 15 and so on..</p>
  
  <p>You may assume that an elephant can only live a maximum of M years. (Not a part of the question, but we may need it to represent algorithmic complexity.)</p>
  
  <p>Given this data, <strong>find the year in which the maximum number of elephants lived</strong>. 
  Resolve ties arbitrarily. </p>
  
  <p>I have tried several approaches to this, but nothing substantial seems to beat the naive solution's complexity. The naive solution is:-</p>
  
  <pre><code>1. Maintain an array(call it ctr).
  2. For every set you encounter, 
      increment all values of ctr in that range.
  3. Once you have traversed all sets, 
      find the index with the highest value in ctr.
  </code></pre>
  
  <p>It's easy to see that the complexity will be O(N*M). </p>
  
  <p>Can anyone offer a better solution?</p>
  
  <p>An alternative question is: Is there a data structure in which you can change a range of values in O(1) time? In an array, to modify k elements, you clearly require O(k) time. Anything better?</p>