title: find common point inside different intervals
body: <p>Given a list of "threads", which contain 2 variables - starting and ending times - implement a function that will return all running threads at some time t. Optimize it.
  (faster than O(n) )</p>
  
  <hr>
  
  <p>My solution was to iterate through the list -- which is O(n). Does anyone know how to achieve faster than O(n) here?</p>
  
  <pre><code>class MyThread{
  Thread thread;
  long start;
  long end;
  }//the object in the list
  
  //function to find "threads"
  public List&lt;Thread&gt; matchingInterval(List&lt;MyThread&gt; list) {
      List&lt;Thread&gt; found = new ArrayList&lt;Thread&gt;();
      Set&lt;Thread&gt; runningThreads = Thread.getAllStackTraces().keySet();
      long instant = System.currentTimeMillis();
      for(MyThread el: list)
          if(el.start &lt;= instant &amp;&amp; el.end &gt;= instant &amp;&amp; runningThreads.contains(el.thread))
              found.add(el.thread);
      return found;
  }
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>The goal is to <code>return all running threads at some time t.</code> My solution assumes <code>time t</code> to be the time (plus/minus error) when my function is called, hence my <code>long instant = System.currentTimeMillis();</code> Is it possible that the caller specifies some arbitrary time? If yes, then I observe that the question really has nothing to do with threads per se and so I don't need to grab the actual <code>runningThreads</code>.</p>
  
  <p>Another point: Just because a thread is alive, is it running?</p>