システムの仕様を競技プログラミングの問題風に帰着して解決してみた

はじめに

こんにちは。AI サービス開発部の千坂です。
主に AI Camera のクライアント側アプリの開発をしています。

AI Camera は、AI による画像解析技術を用いてカメラ画像を解析し様々な課題を解決するサービスです。
例えば、あらかじめ設定した進入禁止エリアに人が侵入したことを自動的に検出してアラートを上げる「侵入検出」機能を利用することで、監視カメラを人が常時監視する必要がなくなります。

アラートが発生した時点の状況を後から確認するために、カメラから取得した画像はストレージに保存します。
すべての画像を保存しているとストレージが不足してしまうため、保存した画像を削除する処理を定期的に行います。
本記事では、削除する画像を選択する処理を競技プログラミングの問題風に設計していきます。

課題

まずは、実装する機能の仕様を決めていきます。

アラートが発生した時点の状況を確認したいので、アラートが発生した時刻およびその前後の画像は削除対象にせず、それ以外の画像を削除対象とします。
ストレージは有限なので、十分に古い画像はアラートの有無に関わらず削除対象とします。
削除処理を行った直後にアラートが発生した場合にもその前後の画像が残っている必要があるため、十分に新しい画像はアラートの有無に関わらず削除対象にしません。

この仕様において削除対象とする範囲を表したのが以下の図です。
赤が削除対象とする範囲で、緑が削除対象としない範囲です。
削除対象とする赤の範囲を求めるのが今回の課題です。

f:id:optim-tech:20200901172118p:plain — 画像を削除対象とする範囲

問題の定式化

「古い」画像を削除することと「新しい」画像を削除しないことは明らかなので、その間で削除対象とする範囲を求めます。
その範囲を $[0, m]$ とします。
$n$ 件のアラート情報があり、それぞれ時刻 $[a_i, b_i ] (1 \le i \le n , a_i \lt b_i)$ の範囲を削除対象から除外することを表します。
どのアラートの範囲にも含まれない時刻の範囲をすべて求めてください、という問題になります。

解法1

削除対象の候補リストを $\{[0, m]\}$ で初期化し、そこから $[a_i, b_i]$ を順次引いていくことを考えます。

$m = 10$ 、 $n = 3$ , $a_i$ と $b_i$ を $\{[1, 3], [5, 7], [7, 9]\}$ とした場合を考えます。
まず、リストを $\{[0, 10]\}$ で初期化します。
そこから最初のアラートの区間 $[1, 3]$ を引くと、リストは $\{[0, 0], [4, 10]\}$ となります。
次の区間 $[5, 7]$ を引くと、リストは $\{[0, 0], [4, 4], [8, 10]\}$ となります。
最後の区間 $[7, 9]$ を引くと、リストは $\{[0, 0], [4, 4], [10, 10]\}$ となり、これが削除対象となる範囲です。

区間を1つ引くたびに候補リストの要素数は最大で1つ増えるため、計算量は $O(n^ 2)$ となります。
※工夫すればこの方針でも計算量を落とせますが、別の方針を採用しました（解法2）。

f:id:optim-tech:20200901182039p:plain — O(n²) のイメージ

解法2

では、以下のような方法ではどうでしょうか。

まず、 $a_i, b_i$ を昇順にソートします。
適当な変数 $x$ を用意し、 $0$ で初期化します。
ソートした列を走査して、それが区間の先頭 $(a_i)$ であれば $x$ に $1$ を加算し、終端 $(b_i)$ であれば $1$ を減算します。
走査中、 $x$ の値が $0$ となっている区間が求める区間となります。

解法1の場合と同様に、 $m = 10$ 、 $n = 3$ , $a_i$ と $b_i$ を $\{[1, 3], [5, 7], [7, 9]\}$ とした場合を考えます。
$a_i, b_i$ をソートします。区間の先頭か終端かが分かるようにするために $a$ または $b$ を付けて書くと、 $\{a1, b3, a5, a7, b7, b9\}$ となります。
$x$ を $0$ で初期化します。
ソートした列の最初が $a1$ なので、その前の $[0, 0]$ の範囲は削除対象です。
$a1$ で $x = 1$ となるため、 $[1, 3]$ の範囲は削除対象ではありません。
$b3$ で $x = 0$ となるため、 $[4, 4]$ の範囲は削除対象です。
$a5, a7, b7$ でそれぞれ $x = 1, 2, 1$ となるため、 $[5, 7], [7, 7], [7, 9]$ の範囲は削除対象ではありません。
$b9$ で $x = 0$ となるため、 $[10, 10]$ の範囲は削除対象です。
以上から、削除対象は $\{[0, 0], [4, 4], [10, 10]\}$ となり、解法1の結果と一致します。