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

ある会議室を使いたい $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$ つの会議室を使いたい $9$ 件の予約に番号 $1$〜$9$ が付いており、それぞれの利用時間は次の半開区間 $[s,f)$（開始時刻 $s$ から終了時刻 $f$ の直前まで）である。

利用時間が重ならない予約をできるだけ多く選ぶために、次の貪欲法を使う（ある予約の終了時刻と別の予約の開始時刻が等しい場合は重ならないとみなす）。

1. 予約を終了時刻 $f$ の小さい順に並べる。
2. 直前に選んだ予約の終了時刻を $t$ とする（最初は $t=-\infty$）。並べた順に予約を 1 つずつ見て、開始時刻 $s$ が $s\ge t$ を満たせばその予約を選び、$t$ をその予約の終了時刻に更新する。満たさなければ選ばない。

この貪欲法によって選ばれる予約の番号の集合を求めよ。

ある人が、テレビ番組を $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$ 件は無条件に）選び、そうでなければ選ばない。」

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

$6$ 種類の文字 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{E},\mathrm{F}$ からなる長さ $45$ の文字列があり、各文字の出現回数は次のとおりである。

この文字列を、次の貪欲法（ハフマン符号の構成法）で作った $2$ 進符号で符号化する。

• 各文字を、出現回数を重みとする $1$ 頂点だけの木とする。
• 木が $2$ 本以上ある間、重みが最も小さい木と $2$ 番目に小さい木を取り出し、それらを左右の子とする新しい根を作って $1$ 本の木にまとめる。新しい木の重みは $2$ つの木の重みの和とする（重みが等しい木が複数あるときは、どれを選んでもよい）。
• 最後に残った木で、根から各文字の葉までの道の各辺に、左の子へ進む辺は $0$、右の子へ進む辺は $1$ を割り当て、その道に沿って並べた $0,1$ の列をその文字の符号語とする。

文字列の各文字をその符号語に置き換えて並べたとき、得られる $0,1$ の列の長さ（ビット数）を求めよ。