JavaScriptで蟻本 貪欲法 区間スケジュール

概要

アルゴリズムの学習記録を投稿します。
今回は蟻本p43・貪欲法の区間スケジュールについてです。

問題

以下引用　蟻本 p43

>n個の仕事があります。各仕事は、時間siに始まり時間tに終わります。
>あなたは各仕事について、参加するか参加しないかを選ばなければなりません。
>仕事に参加するならば、その仕事の初めから終わりまで参加しなければなりません。
>また、参加する仕事の時間帯が重なってはなりません（開始の瞬間・終了の瞬間だけが加算されるのも許されません。）

コード部分

/**
2	 * 貪欲法2 p43  空間スケジューリング
3	 * @param number{Number} 区間の数
4	 * @param start{Array[Number]} 区間の始まり
5	 * @param termination{Array[Number]} 区間の終わり
6	 * @return {Number} 参加した区間の数
7	 */
8	const  scheduling = (number,start,termination) =>{
9	    let stArray = new Array(number)
10	    const START_NUM = 0
11	    const END_NUM = 1
12	    let ans = 0;
13	    for(let i=0;i<number;i++){
14	        stArray[i] = [start[i],termination[i]]
15	    }
16	    // tに対して昇順ソート
17	    stArray = stArray.sort((a,b) => a[1] - b[1])
18	    let tempT = stArray[0][END_NUM]
19	    ans++;
20	    let loopCount = 0;
21	    console.log(`貪欲法2 区間スケジューリング 状態遷移図`);
22	    console.log(`ループ数|i|tempT < stArray[i][START_NUM]|ans|`);
23	    console.log(`--|---|-----|----`);
24	    // i=0のときからスタート
25	    for(let i=0; i<number;i++){
26	        // 現在の区間終わりよりも値が大きい区間始まりを探索する
27	        if(tempT < stArray[i][START_NUM]){
28	            tempT = stArray[i][END_NUM]
29	            ans++;
30	            console.log(`${loopCount} | ${i} |${tempT} < ${stArray[i][START_NUM]} 〇 |${ans}`);
31	        }else{
32	            console.log(`${loopCount} | ${i} |${tempT} < ${stArray[i][START_NUM]} × |${ans}`);
33	        }
34	    }
35	    return ans;
36	}
37	
38	// 結果は3
39	scheduling(5,[1,2,4,6,8],[3,5,7,9,10]);

python tutor

コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。

リンク

その他情報

一言

何を基準に仕事を選ぶのが難しいポイントだと思いました。
反例を探すことが大事（それが難しい！）

依存関係グラフ

依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。

状態遷移図

計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。

表からは0番目、２番目、４番目が選ばれたことがわかります。

i	tempT < stArray[i][START_NUM]	ans
0	3 < 1 ×	1
1	3 < 2 ×	1
2	7 < 4 〇	2
3	7 < 6 ×	2
4	10 < 8 〇	3

参考資料

プログラミングコンテストチャレンジブック [第2版]　マイナビ　p43

プログラマー脳　秀和システム
p73 python tutor
p71 状態遷移表　
p69 依存関係グラフ

githubコミット部分