区間の結合を説明する
Linden Roomsは、1つの部屋について重なる予約を結合する必要があります。入力は整数の分単位の半開区間[start, end)で、隣接する区間は別々のままにする必要があります。アルゴリズムを説明し、そのエッジケースを声に出して順に確認してください。
ルーブリックと準備求められる内容: mid レベルの回答 · 準備に3レッスン
ミドル の基準
- 前提、方法、結果を結び付けてください:結合のルールはその契約に依存するので、私は各区間の開始が終了より小さく、すべてが同じ部屋と時間の基準を共有していることを確認します。半開区間では、終了が次の開始と等しくても重なりません。私は空の入力を空の出力と定義します。
- 結果を左右するエッジケースをテストしてください:[1,8)、[2,3)、[8,10)については、入れ子の区間で終了が縮むことはなく、隣接は重なりではないので、私は[1,8)と[8,10)を残します。私は重複、区間が1つの場合、空の入力もテストし、端点が逆になったものは拒否します。
- 責任を持つ検証や運用のチェックを説明してください:並べ替えにはO(n log n)、走査にはO(n)かかります。すべての区間が離れていることもあるので、出力にはO(n)の空間が必要になることがあります。入力が並べ替え済みだと保証されていれば、結合をストリームで処理できますが、それでも順序を検証するか、明示的な契約に頼ります。