FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の貪欲法で選択される仕事数はどれか。各行は{開始時刻, 終…
問題
次の貪欲法で選択される仕事数はどれか。各行は{開始時刻, 終了時刻}で、終了時刻の昇順に並んでいる。
整数型の二次元配列: job ← {{1,3}, {2,5}, {4,7}, {6,8}, {7,9}}
整数型: i, lastEnd ← 0, count ← 0
for (i を 1 から jobの行数 まで 1ずつ増やす)
if (job[i][1] ≧ lastEnd)
count ← count ＋ 1
lastEnd ← job[i][2]
endif
endfor
return count- ア 2
- イ 3（正解）
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
終了時刻の早い順に見て、開始時刻がlastEnd以上なら選択します。選択したらlastEndをその仕事の終了時刻へ更新します。
| 仕事 | 判定 | lastEnd | count |
|---|---|---|---|
| {1,3} | 選択 | 3 | 1 |
| {2,5} | 除外 | 3 | 1 |
| {4,7} | 選択 | 7 | 2 |
| {6,8} | 除外 | 7 | 2 |
| {7,9} | 選択 | 9 | 3 |
終了時刻と同じ時刻に始まる仕事は選べるため、{7,9}も選択されます。
選択肢の見分け方：2は最後の{7,9}を除外した誤り、4や5は重なる仕事まで選んだ誤りです。開始時刻がlastEnd以上なら選択できるという条件を使いましょう。
このアルゴリズムの正体：これは区間スケジューリング問題を解く典型的な貪欲法で、「終了時刻が早い仕事から順に、前の仕事と重ならなければ選ぶ」という方針です。終了時刻でソート済みなら線形時間で走査でき、この方針で選んだ結果は選択できる仕事数が最大になることが証明されています。条件が「以上(≧)」なのは、前の仕事が終わった瞬間に始まる仕事を許す境界の扱いで、{7,9}が選ばれる根拠になっています。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。