iOS の予約競合を検証する：半開区間と走査線アルゴリズム

予約一覧では2件の会議がちょうど入れ替わるように並んでいるのに、登録時には競合と判定される。別のケースでは、長い予約が短い予約3件をすべて内包しているのに、集計画面の最大同時予約数が1件になっている。どちらも、最初に画面を調べる必要はありません。クラウド Mac 上で区間計算を純粋な Swift 関数として切り出し、境界条件と正解値を固定すれば、不具合を再現可能な入力に絞り込めます。ここで扱うのは単一リソースの占有時間であり、日付表示やネットワークリクエストは対象外です。

まず半開区間の契約を決める

各予約は [start, end) で表します。開始時刻を含み、終了時刻は含みません。そのため、[0, 10) と [10, 20) は競合せず、[0, 10) と [9, 20) は競合します。時刻の単位は秒でも分でも構いませんが、1回の計算では単位を統一し、異なる精度の値をそのまま混在させないでください。

入力の受け取り時点で、終了が開始以前になっているデータを拒否します。長さゼロのリマインダーはリソースを占有する予約ではないため、別のデータモデルで扱うべきです。並べ替えに参加させるために、こっそり1秒を足してはいけません。

「占有区間の統合」と「最大同時占有数の計算」は別の問題です。統合すると重なりの数が失われるため、先に統合してから同時占有数を求めることはできません。

業務上、会議と会議の間に準備時間が必要なら、その時間を占有区間に反映してから同じルールを適用します。画面側だけに追加の判定を入れると、一覧と登録 API で結果が食い違います。

単独で実行できるコア実装を書く

以下を Intervals.swift として保存します。使用するのは標準ライブラリだけです。区間の統合では、実際に重なっている区間だけをつなぎ、端点が接しているだけの区間は重複と見なしません。ここでは、アルゴリズムと日時変換をまず切り離すため、整数の時刻値を使います。

typealias Slot = Range<Int>

func merged(_ input: [Slot]) -> [Slot] {
    precondition(input.allSatisfy { !$0.isEmpty })
    let sorted = input.sorted {
        if $0.lowerBound == $1.lowerBound {
            return $0.upperBound < $1.upperBound
        }
        return $0.lowerBound < $1.lowerBound
    }
    var result: [Slot] = []
    for slot in sorted {
        if let last = result.last,
           slot.lowerBound < last.upperBound {
            result[result.count - 1] =
                last.lowerBound..<max(last.upperBound, slot.upperBound)
        } else {
            result.append(slot)
        }
    }
    return result
}

func peak(_ input: [Slot]) -> Int {
    precondition(input.allSatisfy { !$0.isEmpty })
    let events = input.flatMap {
        [(time: $0.lowerBound, delta: 1),
         (time: $0.upperBound, delta: -1)]
    }.sorted {
        if $0.time == $1.time {
            return $0.delta < $1.delta
        }
        return $0.time < $1.time
    }
    var active = 0
    var maximum = 0
    for event in events {
        active += event.delta
        maximum = max(maximum, active)
    }
    return maximum
}

precondition(merged([]).isEmpty)
precondition(peak([]) == 0)
precondition(merged([0..<10, 10..<20]) == [0..<10, 10..<20])
precondition(peak([0..<10, 10..<20]) == 1)
precondition(merged([0..<10, 5..<15, 10..<20]) == [0..<20])
precondition(peak([0..<10, 5..<15, 10..<20]) == 2)
precondition(merged([0..<30, 5..<10, 8..<12]) == [0..<30])
precondition(peak([0..<30, 5..<10, 8..<12]) == 3)
precondition(peak([0..<10, 0..<10]) == 2)

ターミナルで実行します。

xcrun swift Intervals.swift

すべての検証を通過すると、何も出力されず、終了コードはゼロになります。assert だけでなく precondition を使うのは、通常の最適化ビルドでアサーションが無効になり、テストが実質的に機能しなくなるのを避けるためです。検証スクリプトにも、安全性チェックを無効にするコンパイルオプションは使わないでください。

同時刻のイベントと入れ子の区間を検証する

走査線アルゴリズムでは、開始をプラス1、終了をマイナス1のイベントとして扱います。同じ時刻では、必ず減算を先に、加算を後に処理します。逆にすると、隣接する2件の予約を一瞬だけ同時に存在するものとして数えてしまいます。時刻だけでソートし、同時刻の処理順を明示しない実装は、典型的な境界バグの原因です。

固定のテストケースとして、少なくとも空のリスト、端点で接する区間、部分的な重なり、完全な包含、完全な重複の5種類を残してください。同一の区間が2件の独立した予約を表すかどうかは、業務上の入力の意味によります。この記事では各要素を1件の占有として扱うため、完全に重複する2件の同時占有数は2です。

統合アルゴリズムには、もう1つ見落としやすい点があります。右端の更新では、必ず大きいほうの値を採用することです。現在の区間の終了値で単純に上書きすると、長い予約が短い予約を内包している場合に、統合結果がかえって短くなります。また、入力の順序が変わっても結果は同じでなければなりません。サーバーがたまたまソート済みのデータを返すことに依存しないようにします。

別の計算方法で突き合わせる

固定ケースだけでは、実装と一緒に「正解値」まで間違えてしまうことがあります。狭い範囲の整数サンプルなら、各時刻値を含む区間を1つずつ数え、独立した参照計算にできます。以下のコードを同じファイルの末尾に追加すれば実行できます。これはテスト用であり、本番のアルゴリズムを置き換えるものではありません。

func referencePeak(_ input: [Slot]) -> Int {
    guard let start = input.map(\.lowerBound).min(),
          let end = input.map(\.upperBound).max() else {
        return 0
    }
    return (start..<end).map { tick in
        input.filter { $0.contains(tick) }.count
    }.max() ?? 0
}

let candidates: [Slot] = (0..<5).flatMap { start in
    ((start + 1)...5).map { start..<$0 }
}

for first in candidates {
    for second in candidates {
        let sample = [first, second]
        precondition(peak(sample) == referencePeak(sample))
        precondition(merged(sample) ==
                     merged(Array(sample.reversed())))
        precondition(merged(merged(sample)) == merged(sample))
    }
}

この3つのチェックは、それぞれ同時占有数の正しさ、入力順序への非依存性、統合の冪等性を検証します。この離散的な参照アルゴリズムが適用できるのは、ここで定めた整数の時刻値という契約だけです。任意の連続時間まで検証できたとは言えません。ランダムテストを追加する場合は、乱数シードの記録だけで済ませず、失敗した入力そのものを保存してください。ツールチェーンが変わった後でも再現しやすくなります。

組み込み前に入力検証と失敗記録を整える

実際のプロジェクトへ組み込む際は、解析、正規化、区間計算を3つの層に分けます。まず開始と終了を同じ時間基準にそろえ、次に精度を統一し、最後に終了が開始より厳密に後であることを確認します。精度の変換によって、もともと短かった予約の長さがゼロになる場合があるため、変換前だけの検証では不十分です。

複数の会議室が同じ予約一覧を共有するなら、先にリソース識別子でグループ分けし、それぞれについて計算します。別々の会議室で同時に開かれる会議を、互いに競合させてはいけません。人についても同時予約を禁止する必要があるなら、人物用のリソース制約を別に設けます。すべての予約を無条件に1本の走査線へ混ぜないでください。

失敗時の記録には、リソース識別子、正規化後の区間、期待値、実際の値、ツールチェーンのバージョンがあれば十分で、参加者情報を添える必要はありません。修正する前に、その入力を固定テストケースへ追加し、スクリプト全体を実行します。最終的な合格条件は、境界ケース、参照計算、業務上のグループ分けがすべて整合することです。特定の画面で競合の警告が出なくなっただけでは、検証完了とは言えません。

よくある質問