FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：終了時刻の早い順に並んだ作業を、重ならないように貪欲に選ぶ。…
問題
終了時刻の早い順に並んだ作業を、重ならないように貪欲に選ぶ。戻り値はどれか。配列の要素番号は1から始まる。
整数型の配列: start ← {1, 2, 4, 6, 7}
整数型の配列: finish ← {3, 5, 6, 8, 9}
整数型: i, last ← 0, count ← 0
for (i を 1 から startの要素数 まで 1 ずつ増やす)
if (start[i] ≧ last)
count ← count ＋ 1
last ← finish[i]
endif
endfor
return count- ア 2
- イ 3（正解）
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
開始時刻が現在のlast以上なら採用し、lastをその作業の終了時刻へ更新します。
作業1は採用してlast=3。作業2は2<3なので不採用です。作業3は4≧3で採用してlast=6。作業4は6≧6で採用してlast=8。作業5は7<8なので不採用です。合計3件になります。
Hardでの確認点：貪欲法では、なぜその順番で見てよいかを意識しましょう。終了時刻順に並んでいるため、選べる作業を見つけたら採用してlastを更新します。開始時刻がlastと等しい場合を許すかどうかも条件式で確認しましょう。
このアルゴリズムの正体：これは区間スケジューリング問題で、終了時刻が早い作業から選ぶ貪欲法は「選べる最大件数」を必ず得られる最適解と証明されています。配列が終了時刻順に整列済みのため走査は一度きりで、計算量はO(n)です。今回はlast=3,6,8と更新され3件が最大で、より多く選べる組合せは存在しません。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。