アルゴリズムと計算量の問題

ある会議室を使いたい $9$ 件の予約希望があり、予約 $k$（$k=1,2,\dots ,9$）は時刻 $s_k$ に始まり時刻 $f_k$ に終わる（区間 $[s_k,f_k)$ を使う）。

$2$ つの予約 $i,j$ は、$f_i\leqq s_j$ または $f_j\leqq s_i$ のとき両立する（同時に採用できる）とする。次の貪欲法で、互いに両立する予約を選ぶ。

• 予約を終了時刻 $f_k$ の小さい順に並べる。
• その順に予約を $1$ つずつ調べ、それまでに選んだどの予約とも両立するならば選び、そうでなければ選ばない。

この貪欲法で選ばれる予約の番号 $k$ の集合を求めよ。

ある人が、テレビ番組を $1$ 台のテレビで $1$ 本ずつ見ることにした。見たい番組が $8$ 本あり、番号 $1$〜$8$ が付いている。番組 $k$ の放送時間は、開始時刻 $s_k$ から終了時刻 $f_k$ の直前までの半開区間 $[s_k,f_k)$ である（時刻の単位は時間）。

番組は最初から最後まで見るものとし、放送時間が重なる $2$ 本を両方見ることはできない（一方の終了時刻ともう一方の開始時刻が等しい場合は、両方見られる）。

次の貪欲法で見る番組を選ぶ。

• 番組を終了時刻 $f_k$ の小さい順に並べる。
• その順に番組を調べ、その番組の開始時刻が、すでに選んだ番組の終了時刻の最大値以上であれば（まだ $1$ 本も選んでいなければ無条件に）その番組を選ぶ。そうでなければ選ばない。

この貪欲法で選ばれる番組の番号の集合を求めよ。

ある天文台には天体望遠鏡が $1$ 台しかなく、$7$ 件の観測希望（番号 $1$〜$7$）が出ている。観測希望 $k$ は時刻 $s_k$ に始まり時刻 $f_k$ に終わり、半開区間 $[s_k,f_k)$（$s_k$ 以上 $f_k$ 未満）の間、望遠鏡を使う。時刻は整数で表し、ある観測の終了時刻と別の観測の開始時刻が等しい場合は、両方とも行うことができる。

次の貪欲法で、互いに時間が重ならない観測希望を選ぶ。

「観測希望を終了時刻 $f_k$ の早い順に並べ、先頭から順に見ていく。その観測希望の開始時刻が、すでに選んだ観測希望のうち最後に選んだものの終了時刻以上であれば（最初の $1$ 件は無条件に）選び、そうでなければ選ばない。」

この貪欲法によって選ばれる観測希望の番号の集合を求めよ。

ある科学フェスティバルで、$8$ つの体験教室 $1$〜$8$ が開かれる。体験教室 $k$ は時刻 $s_k$ に始まり時刻 $f_k$ に終わり、半開区間 $[s_k,f_k)$ の時間帯を使う（したがって、ある教室の終了時刻と別の教室の開始時刻が等しければ、両方に参加できる）。

ある参加者は、時間帯が重なる $2$ つの教室には同時に参加できない。この参加者が次の貪欲法で参加する教室を選ぶ。

「教室を終了時刻の早い順に並べ、先頭から順に見ていく。見ている教室の開始時刻が、直前に選んだ教室の終了時刻以上であれば（最初の教室は無条件に）その教室を選ぶ。そうでなければ選ばない。」

この貪欲法で選ばれる教室の番号の集合を求めよ。

$1$ つの会議室を使いたい $10$ 個の予約 A〜J がある。予約 X の開始時刻を $s_X$、終了時刻を $f_X$ とし、予約 X は時間帯 $[s_X,f_X)$（$s_X$ 以上 $f_X$ 未満）に会議室を使う。

$2$ つの予約 X, Y は、$f_X\le s_Y$ または $f_Y\le s_X$ のとき、同時に採用できるものとする。次の貪欲法で予約を採用する。

1. 予約を終了時刻 $f_X$ の小さい順に並べる。
2. その順に予約を $1$ つずつ調べ、すでに採用した予約のどれとも同時に採用できるならば採用し、そうでなければ採用しない。

この貪欲法で採用される予約をすべて選び、その記号をアルファベット順に「,」で区切って答えよ（解答例：A, D, G）。