[알고리즘] Activity selection : 정의 & d.p algorithm

(2021.10.27)

알고리즘 수업들으면서 정리하기 15탄

 

 

---

 

Activity selection

:공통의 자원에 대한 독점적인 사용을 필요로 하는 활동 N개가 있는데 이를 어떻게 스케줄링 할 것인가 하는 문제를 말한다.

ex) 교실의 대한 사용을 스케줄링 하는 문제

 

Problem: 여러 competing activities 사이의 스케줄을 조정하는 것 ( 각 activity에 대해서 시작과 종료시간은 주어짐)

Goal: nonoverlapping activities 의 largest possible set을 선택함

 

 

 

이와 같은 결과를 도출할 수 있음

 

 

 

 

이를 이제 dynammic programming 기법으로 접근해보겠다

 

 

 

 

 

 

 

 

 

 

greedy algorithms으로 접근하는 건 다음 시간..