[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[mhc:01322] Re: conflict detection

  From:       Yoshinari Nomura <nom@xxxxxxxxxxxxxxxxxxx>
  Subject:    [mhc:01321] Re: conflict detection
  Date:       Wed, 4 Apr 2001 18:42:55 +0900
  Message-Id: <20010404184255R.nom@xxxxxxxxxxxxxxxxxxx>

  | > n個の区間データを蓄積されているときに、区間を入力してそれが
  | > 蓄積データと衝突しているかどうかの判定がO(n log n)ということです。
  | 
  | あら。ここ (interval search) は、O(log n) だと思ってました。
  | それで、今回のケースでは、蓄積しているデータ n 個について
  | さらに調べるから O(n log n) なんだと理解していました。

指がすべってしまいました。乃村さんのおっしゃるとおりです。

あと、実装は二分木だと書きましたが、
あれは二分探索木と呼ぶのが正しいです。
本を読みなおして気づきました。

でもって、へぼいあたまでいろいろ妄想したけっか
同じbeginならendを持たないスケジュールの方が先(または後)になるよう
ソートするしか解決方法はないように思えました。

--
KOIE Hidetaka 鯉江英隆 <hide@xxxxxxxx>