[그리디] 간격 스케줄링 알고리즘(Task Scheduling, Activity Selection Problem)(예제: 백준 1931)

[목차]

1. Task Scheduling Problem이란?
2. Task Scheduling 알고리즘
   
   1. Dynamic Programming 알고리즘
   2. Greedy 알고리즘
3. 예제

---

1. Task Scheduling Problem이란?

예제로는 [백준 1931번 회의실 배정]이 있다.

 

2. Task Scheduling 알고리즘

1) DP

2) Greedy

나중에 다른 그리디 문제를 풀 때에도 내가 떠올린 그리디 알고리즘이 올바른지 확인할 때 지금 당장 손해를 보더라도 나중 가서는 이득인 경우가 있을 수는 없는지 고민해보면 정당성을 확인하거나 반례를 찾을 때 도움이 됩니다. 

3. 예제

유명한 예제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정