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
正解：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と等しい場合を許すかどうかも条件式で確認する。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。