algorithm - ばらばらな間隔のセットに Interval を挿入する

Answer 1

あなたの質問と例は、重複しない間隔を暗示しています。この場合、二分探索を実行するだけです。比較が開始時刻で行われるか終了時刻で行われるかは、重複しない間隔では問題になりません。まだ存在しない場合は、見つかった位置に新しい間隔を挿入します。

アップデート

最初の例で発生したマージを見逃しました。悪いケースは、長い間隔が多くの短い間隔と重なる短い間隔の長いリストに大きな間隔を挿入することです。マージする必要があるすべての間隔の線形検索を回避するには、2 つのバイナリ検索を実行できます。1 つは開始時間で比較する左から、もう 1 つは終了時間で比較する右からです。

ここで、間隔が存在するか、挿入する必要があるか、2 つの検索で見つかった位置間の間隔とマージする必要があるかを判断するのは簡単です。これはそれほど複雑ではありませんが、おそらくオフバイワンエラーが非常に発生しやすく、テストが必要です。