[알고리즘 문제]/탐욕기법/Deadline이 주어진 작업의 scheduling

머리를 약간 써야 하는 문제입니다.

알고리즘 실기 시험 시간에 나온 문제인데 4시간안에 5문제를 풀어야하는데

이문제 생각이 잘 나지 않아서 못풀었네요.

푸는 방법은 탐욕기법을 이용하여 풉니다.(푸는방법 보지말고 풀어보세요 그게 도움이 될듯)













먼저, profit이 높은것으로 먼저 정렬을 합니다.

위의 예를 가지고 하면

                    job5  job2  job1  job4  job3 
profit              16      12    10     7      4
deadline          2       13    4      2      1

 

이렇게 되겠죠 .
그럼 작업을 하나씩 넣습니다 정렬한 순서대로 

day	1	2	3	4	5	6	7	8	9	10	11	12	13
jobnum		job5

 위처럼 job5가 먼저 들어가겠죠. deadline에 맞춰서 넣습니다.

day	1	2	3	4	5	6	7	8	9	10	11	12	13
jobnum		job5											job2

 job2를 넣습니다.

day	1	2	3	4	5	6	7	8	9	10	11	12	13
jobnum		job5		job1									job2

 
job1를 넣습니다.

day	1	2	3	4	5	6	7	8	9	10	11	12	13
jobnum	job4	job5		job1									job2

 job4를 넣는데 job4의 deadline인 2에는 이미 다른 job이 들어가있습니다. 그러면 위와같이 그앞 day에다가 넣습니다.

day	1	2	3	4	5	6	7	8	9	10	11	12	13
jobnum	job4	job5		job1									job2

마지막으로 job3를 넣어야하는데 넣을곳이 없기때문에 job3는 작업을 하지 않습니다. 그래서

job4->job5->job1->job2

이 순서대로 실행을 하게 됩니다.

푸는방법만 알면

짜는것은 금방 할듯하네요