問題の概要と適用範囲
半開区間 [left, right) に対する3つの操作（カバー範囲の追加、クエリ区間が完全にカバーされているかの判定、カバー範囲の削除）を実装します。公開されている Range Module の問題と同様に、1 <= left < right <= 10^9 および最大 10^4 回の呼び出しを想定します。API が防御的な入力を受け入れる場合に left >= right となった際の挙動を明記してください。
面接官が見ているポイント
最大の評価点は、区間の挿入、削除、クエリが行われる中で、データ構造の不変条件（インバリアント）を適切に選択し維持できるかどうかです。期待される表現は、互いに素な区間のソート済み正規化コレクションです。LeetCode では順序付きセット（ordered set）やセグメント木（segment tree）が関連アプローチとして挙げられています。Magicsheet ではこの問題を Hard と分類し、ordered set や segment tree のタグを付けています。また、この問題では半開区間の境界処理の規律、イテレータの安全性、計算量の見積もりも試されます。
確認すべき質問
- 端点は閉区間（両端を含む）ですか？ 本回答では
[left, right)を使用します。 [1,3)と[3,5)のように接している区間はマージすべきですか？ 本回答では1つの正規化された区間にマージします。- 実行前にすべての端点が既知ですか？ 基本設計はオンライン処理であるため、事前には分かりません。
- 無効な
left >= right入力に対してはどう振る舞うべきですか？ 状態を変更せずにリターンするか、明示的に拒否します。 - 座標ドメインは、セグメント木を採用するのを正当化できるほど有界かつ静的ですか？ これにより代替設計が変わります。
ステップバイステップの解説
1. 表現と不変条件の選択
区間の開始点から終了点への順序付きマップ（ordered map）を使用します。std::map はキーをソートされた状態に保ち、対数時間での検索、挿入、削除を保証します。また、昇順イテレーションにより、アルゴリズムは近傍の区間のみを走査できます。接している区間同士を正規化し、各操作の後にマップ内に previousEnd >= nextStart を満たすペアが存在しないようにします。
2. カバー範囲の追加
終了点が少なくとも left である最初の区間（または先行区間の次の最初の区間）から走査を開始します。現在の開始点が拡張中の right 以下である限り、その区間を含むように left と right を拡大し、その区間に削除マークを付けます。マークされた連続する範囲を削除し、マージされた区間を挿入します。空の状態や、両隣と素である区間には特別な構造は必要ありません。
3. カバー範囲の削除とクエリ
削除の場合、start < right かつ end > left である区間を巡回します。重なりがある各区間について、oldStart < left のときは [oldStart,left) を残し、right < oldEnd のときは [right,oldEnd) を残します。断片を挿入する前に元の区間を削除します。クエリの場合、開始点が left を超えない最大の開始点を持つ区間を調べます。その区間が存在し、かつその終了点が少なくとも right である場合にのみ true を返します。半開区間であるため、[1,3) は [3,4) をカバーしません。
正当性と計算量
不変条件により、帰納法で正当性が証明されます。追加操作は新しい範囲に接続するすべての区間をそれらの和集合に置き換えるため、カバーされた点が失われることはなく、結果は正規化された状態になります。削除操作は各重複部分を、削除範囲外の正確な部分のみに置き換えます。先行区間のクエリで十分な理由は、ソートされた互いに素な区間により、それより前の区間の終了点はより後になることはなく、left より大きい開始点を持つ後続の区間が left を含むことはあり得ないためです。
n を保持されている区間の数、k を更新によって影響を受ける区間の数とします。クエリは O(log n) です。更新は O(log n) の検索に加えて O(k) のイテレータ走査と削除を実行します。各キーを再検索する実装の場合は O(k log n) になることがあります。空間計算量は O(n) です。セグメント木は既知の有界な座標空間に対しては合理的ですが、座標圧縮はすべての端点がオフラインで揃っている必要があり、任意のオンライン呼び出しには適していません。
模範回答
「半開区間で構成される、ソート済みかつ互いに素な正規化順序付きマップを実装します。add は重複または接しているすべての区間を特定してマージし、remove は重複を削除して最大2つの境界断片を保持し、query は要求された開始点の先行区間を確認します。重要な証明義務は、各操作が正規化された和集合を維持することです。クエリの計算量は O(log n) であり、更新は連続するイテレータ範囲を削除する場合に O(log n + k) で、空間計算量は O(n) です。このオンラインマップとセグメント木の比較は、座標ドメインおよびすべての端点が既知であるかを確認した上で行います。」
よくあるミス
- 端点を閉区間として扱う → 隣接する区間が誤って重複しているように見えてしまう → 最初に
[left,right)を定義する。 - 接している区間を分離したままにする → 後続のクエリや更新で余計な重複処理が発生する → 隣接区間を正規化する。
- 無効化されたイテレータをインクリメントしながら削除する → ノードをスキップしたり、解放されたメモリにアクセスしたりする → 次のイテレータを退避させるか、既知の範囲を一括削除する。
- 両端を残さずに分割する → 片方の境界でカバー範囲が消滅してしまう → 中央の削除や完全包含のケースをテストする。
- すべての更新が O(log n) だと主張する → 1つの操作で多数の区間に触れる可能性がある → 計算量の上界に
kを含める。 - オンライン処理で座標圧縮を使用する → 未知の端点によりインデックスが無効になる → 順序付き構造を使用するか、完全なオフライン集合から再構築する。
フォローアップと発展課題
どのような境界ケースをテストすべきか？
空のモジュール、重複した追加、ちょうど端点上でのクエリ、[1,3) の後に [3,5) を追加するような接する追加、中央部分の削除、区間全体を覆う削除、重なりのない削除、入れ子の区間、および API が許可する場合は端点 0 や 10^9 をテストします。
不変条件をどのようにテストするか？
ランダムな各操作の後に、開始点がソートされていること、end > start、および previousEnd < nextStart をアサートします。非常に小さな座標ドメイン上で、クエリ結果を小さなブール配列や総当たり（ブルートフォース）の和集合モデルと比較します。これにより、off-by-one エラーや断片の欠落バグを検出できます。
セグメント木が有利になるのはどのような場合か？
座標空間が有界または圧縮可能であり、区間の集約や遅延伝搬（lazy propagation）が重要となる場合にセグメント木を選択します。予測可能な対数時間の操作が得られますが、ノードや遅延状態の複雑さが増します。疎でオンラインの区間に対しては、順序付きマップの方がシンプルです。