[mhc:01317] Re: conflict detection

[KOIE Hidetaka (鯉江英隆) <hide@xxxxxxxx>]

  From:       Yoshinari Nomura <nom@xxxxxxxxxxxxxxxxxxx>
  Subject:    [mhc:01315] Re: conflict detection
  Date:       Fri, 30 Mar 2001 10:55:05 +0900
  Message-Id: <20010330105505J.nom@xxxxxxxxxxxxxxxxxxx>

  | foo4 が conflict するのに、foo がしないのは、やっぱり変ですね。
  | 走査を簡単にするために、今のロジックは、
  | 
  |   foo (a時 〜 b時), bar (c時 〜 d時) のスケジュールがあったときに、
  |   foo に conflict が付く条件は、
  | 
  |     b, c が設定されていて、かつ b < c   である (1)  または、
  |     b    が設定されていて、かつ b < max である (2)
  | 
  |   max は、foo より前に現れたスケジュールにおける終了時間の最大値。
  | 
  | となっています。
  | 
  | さて、効率を落とさないで鯉江さんの要求を満たすには、
  | どういじればいいかな。。

単純に、ソートするときのキーをaとbの2つにするというのではだめ?

                *                *                *

区間木というデータ構造をつかうと
全conflictを検出できますがコストはO(n log n)になります。

なんにもしないのはあれなので
教科書を見ながらCでサンプルコードを書きました。
ただし教科書では二色木だったところを単なる二分木に省略しましたが
1 conflictの検出コストは木の高さに依存するので
木がバランスしていないとO(log n)になるはずがO(n)に悪化します。

emacs/mhcのコードをぱっと読んだところ
confclictチェックをする前にスケジュールを開始時刻でソートしているので
二分木でもinsertする順序をかしこくすればバランスさせられますね。

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

H4sIAAAAAAAAA2xTUWvCMBB+F/ofDgVJR+cP0M7h3gZuTxsMxhhRTw3URNLoBup/312atN
WuD/bu6919X+6LA6WXxWGFkCtTOotyN9pOk96ghglUekMQgStcK43wMvsQswyeUhBilsIU
BIWPwPGY45SLqe+wdPCsHdqjLJLeKekBPUo7KJ20btLkqFchi+WiLstiBQ/3iPC/acag8B
9OcEl6lwnThkMMKdqjlc7YPBcRBAoyWBpdNsKGoNJanEV3sJrLIM+h/9nnlxp5Qo9kASFa
n3/1ifXCxAtj6JCq/DZHtIXc73ElIgfIrOaDRUOn1iBkNQsWgeV8prCCZAWlVXFL31oWJY
aNIYWdAto9RmHBiDeLWBNzcgcFrqMLFWDVZutunOD1+6Dl107++mXHTtEpbmkeex7x+j6f
k2eeIiaq5XbVlvHsOuU9tCa1bPZ6ad26RLoQQb0xLuvqTm9OrfHH0CV+4KBSX1dOGlt4WK
A+NQril/tpLTHcDbgGWqq9Lb6H90C8QXSDNYuICrrGNlP8Bm/HePD/OVUBrZV6+J97rf8P
AAD//6xVyw6CQAy8m/gPlQORyMEzRvkUYmQTSHhsUNTE+O/uoyztihgTOUHplunMtGiKY/
4Zeo0HDPiUdGJrJrCdOe6jTumTKxANcJ++pR+8DSuaUo/no+l1xmD6a1vmy0Xe1zIrm7bL
RYcmubQyBr4P7IYD2antdufDqbJts0RPVtQlxLaWLQIbCBKVGgyN4ULBt+rOnBs0MJtkHb
i4pkWHIhNSAlU7D5LhDzG940EzfALkEcSmhzIzUsE+4RJjCEhBN5G2p+wsjt2p+G00pRIY
VdTBW1FWAtYSwhBWwFcroY/YfnpiUSJdRlLvHvbzU6vh4IHZucQ8uj25MyVn3XEkmr7WPy
nxF5qmm/9C2wsAAP//pJZNCoMwEIWvMrQbxbTElhbbgssuewHJQvyBLKpS60q8exOjyRhS
oVTQxcgkL5OPN4PLNj9Z3SlcnYiuAfpPxfulCEeRmlWf+35jw++XN97WM+WVZxd/8iHZwV
BHzNN3mrDkwMQvdJAeTgQiGAgOUQJHKxQRuFihM4GQWrFdSMQ7n2fQPbisXzBOTFxsT29K
DWcJZbLiIsCDAE8R6giogRjoPJNL9Doh0xY9OoZKkZj4WsM4sImZbAllxiuIY2jlpzCAbg
Uk1AiasLYg8howuMx+YqltSeH7Nr8Lu2qUUGFW97qr8qsxZTcPM/ybhyhSKVP2mPLtMsNB
qUsh2lGvby1b5bzE+H0AAAD//wMAWL/tc5kLAAA=