異なる間隔内の共通点を見つける

Question

開始時刻と終了時刻の2つの変数を含む「スレッド」のリストがあると、ある時刻tに実行中のすべてのスレッドを返す関数を実装します。それを最適化する。

---

マイ溶液がリストを反復することであった（O（N）よりも速い） - （N）Oです。誰もがO（n）より速く達成する方法を知っていますか？

class MyThread{ 
Thread thread; 
long start; 
long end; 
}//the object in the list 

//function to find "threads" 
public List<Thread> matchingInterval(List<MyThread> list) { 
    List<Thread> found = new ArrayList<Thread>(); 
    Set<Thread> runningThreads = Thread.getAllStackTraces().keySet(); 
    long instant = System.currentTimeMillis(); 
    for(MyThread el: list) 
     if(el.start <= instant && el.end >= instant && runningThreads.contains(el.thread)) 
      found.add(el.thread); 
    return found; 
} 

EDIT：

目標は、私のソリューションは、time tは（プラス/マイナスのエラー）私の関数が呼び出され、それゆえ私のlong instant = System.currentTimeMillis();は、発信者は、いくつかの任意の指定していること、それは可能です時間であることを前提としていreturn all running threads at some time t.にあります時間？はいの場合、私はその質問がスレッドそのものとはまったく関係ないことを観察し、実際にはrunningThreadsを取得する必要はありません。

別のポイント：スレッドが生きているという理由だけで、実行中ですか？

Answer 1

リストがソートされている場合は、任意の検索アルゴリズム（分割や征服など）でO（n）より高速に処理できます。各項目を見なければならないので、ソートされていないリストのO（n）よりも速く達成することはできません。

Answer 2

「最適化」と言えば、リストオーダーの前処理が許可されています。将来のクエリを高速化します。その場合、私はinterval tree（実際にはバイナリ検索ツリーのアプリケーションです）を使用します。