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