区間スケジューリング問題

記号

相異なる $2$ つの整数 $a, b \in \mathbb{Z}$ で $a < b$ をみたすものに対し、 $(a, b) := \{ x \in \mathbb{Z} \mid a < x < b \}$ とおき、開区間 という。

任意の開区間 $I = (a, b)$ に対して、 $s(I) := a,\ t(I) := b$ とおく。

問題（区間スケジューリング問題）

正の整数 $n$ と、 $n$ 個の異なる開区間 $(s_1, t_1),\ \ldots,\ (s_n, t_n)$ が与えられる。互いに交わらないような開区間の組 $(s_{i_1}, t_{i_1}),\ \ldots,\ (s_{i_r}, t_{i_r})$ （ $r$ は正の整数で、各 $1 \leq j \leq r$ に対し $1 \leq i_j \leq n$ ）を選ぶとき、最大で何個の開区間を選ぶことができるか。

$\mathcal{I} := \{ (s_i, t_i) \mid 1 \leq i \leq n \}$ とおく。求めるものを定義する：

定義

$\mathcal{I}$ の部分集合 $\mathcal{J} \subseteq \mathcal{I}$ で次の $2$ 条件をみたすものを $\mathcal{I}$ の good な部分集合という。

  • $\mathrm{(a)}$ 任意の $I, J \in \mathcal{J},\ I\neq J$ に対して $I \cap J = \emptyset$ が成り立つ。
  • $\mathrm{(b)}$ $\mathcal{I}$ の部分集合 $\mathcal{J}' \subseteq \mathcal{I}$ が条件 $\mathrm{(a)}$ をみたすなら $\mathcal{J}' \subseteq \mathcal{J}$ が成り立つ。
定理

次の操作を考える。

  • $1$ 回目の操作： $\mathcal{I}$ の元 $I$ であって $t(I)$ が最も小さいものを $1$ つ選び、 $I_1 := I$ とおく。
  • $i$ 回目 $(i \geq 2)$ の操作： $\mathcal{I}_i := \{ I \in \mathcal{I} \mid t(I_{i-1}) \leq s(I) \}$ とおく。そして、 $\mathcal{I}_i$ の元 $I$ であって $t(I)$ が最も小さいものを $1$ つ選び、 $I_i := I$ とおく。

このとき、次が成り立つ：

  • $\mathrm{(1)}$ ある正の整数 $m$ が存在して、任意の $I \in \mathcal{I}$ に対して $t(I_m) \geq s(I)$ となる。
  • $\mathrm{(2)}$ 集合 $\mathcal{J} := \{ I_i \mid 1 \leq i \leq m \}$ は $\mathcal{I}$ の good な部分集合である。
証明

まず、集合 $\mathcal{I}$ は有限集合だから $\mathrm{(1)}$ が成り立つ。 $\mathrm{(2)}$ を示す。

条件 $\mathrm{(a)}$ をみたすこと： $I_i, I_j \in \mathcal{I},\ i < j$ とする。 このとき、 $t(I_i) \leq s(I_{i+1})$ だから $I_i \cap I_j = \emptyset$ が成り立つ。

条件 $\mathrm{(b)}$ をみたすこと： $\mathcal{I}$ の部分集合 $\mathcal{J}' \subseteq \mathcal{I}$ が条件 $\mathrm{(a)}$ をみたすとする。 このとき、 $\mathcal{J} \subsetneq \mathcal{J}'$ が成り立つと仮定して矛盾を導く。 各 $1 \leq i \leq m$ に対し、 $\widetilde{s}_i := s(I_i),\ \widetilde{t}_i := t(I_i)$ とおく。

仮定より、ある元 $(\widetilde{s}, \widetilde{t}) \in \mathcal{J}' \setminus \mathcal{J}$ が存在する。 すると、 $\mathcal{J}'$ は条件 $\mathrm{(a)}$ をみたすから、仮定より任意の $1 \leq i \leq m$ に対して $I_i \cap (\widetilde{s}, \widetilde{t}) = \emptyset$ である。 よって、次の $3$ つのいずれかが成り立つ：

  • $\mathrm{(i)}$ $\widetilde{t} \leq \widetilde{s}_1$.
  • $\mathrm{(ii)}$ ある $1 \leq i < m$ が存在して $\widetilde{t}_i \leq \widetilde{s}$ かつ $\widetilde{t} \leq \widetilde{s}_{i+1}$.
  • $\mathrm{(iii)}$ $\widetilde{t}_m \leq \widetilde{s}$.
$\because )$

上の $\mathrm{(i)}, \mathrm{(ii)}, \mathrm{(iii)}$ すべてが成り立たないとする。

準備として、各 $1 \leq i < m$ に対して、主張「 $\widetilde{s}_i < \widetilde{t}$ なら $\widetilde{s}_{i+1} < \widetilde{t}$ である」が成り立つことを示す。

証明：もし $\widetilde{s} < \widetilde{s}_i$ なら $I_i \cap (\widetilde{s}, \widetilde{t}) = \emptyset$ に矛盾するから $\widetilde{s}_i \leq \widetilde{s}$ である。 また、もし $\widetilde{s} < \widetilde{t}_i$ なら同じく矛盾だから $\widetilde{t}_i \leq \widetilde{s}$ となる。 よって、いま上の $\mathrm{(ii)}$ の否定を仮定しているから $\widetilde{s}_{i+1} < \widetilde{t}$ でなければならない。（証明終）

上の事実と $\mathrm{(i)}$ の否定を用いれば、数学的帰納法より任意の $1 \leq i \leq m$ に対し $\widetilde{s}_i < \widetilde{t}$ が成り立つ。 特に、 $\widetilde{s}_m < \widetilde{t}$ である。

これと $\mathrm{(iii)}$ の否定を合わせると $\widetilde{s}_m < \widetilde{t}$ かつ $\widetilde{s} < \widetilde{t}_m$ 、すなわち $I_m \cap (\widetilde{s}, \widetilde{t}) \neq \emptyset$ が得られ、矛盾する。

上のいずれの場合でも矛盾することを示す。

$\mathrm{(i)}$ の場合：このとき $\widetilde{t} \leq \widetilde{s}_1 < \widetilde{t}_1$ だから、開区間 $I_1$ の選び方に矛盾する。

$\mathrm{(ii)}$ の場合：このとき $\widetilde{t} \leq \widetilde{s}_{i+1} < \widetilde{t}_{i+1}$ だから、開区間 $I_{i+1}$ の選び方に矛盾する。

$\mathrm{(iii)}$ の場合：定理の $\mathrm{(1)}$ より矛盾。

以上の議論により仮定 $\mathcal{J} \subsetneq \mathcal{J}'$ から矛盾が導かれ、 $\mathcal{J}' \subseteq \mathcal{I}$ が成り立つことがわかった。

定理の $\mathrm{(2)}$ により、上の操作で得られた正の整数 $m$ が冒頭の区間スケジューリング問題の答えとなることがわかる。