[그리디] 회의실 배정

1. 먼저 문제에서 원하는 것을 찾는다.

문제의 핵심 조건은 : 

회의가 겹치지 않게 하면서 최대한 많은 회의를 선택한다. 

 

즉, 

- 입력: 여러 개의 회의

- 선택: 회의들을 골라야 함

- 제약: 서로 겹치면 안 됨

- 목표: 선택 개수 최대화 

 

 

2. 모든 경우의 수 생각

회의가 5개라고 할 때 

A  1 ~ 4
B  2 ~ 5
C  4 ~ 7
D  5 ~ 6
E  6 ~ 8

 

각 회의를 선택할지 말지 결정해야 하니까 단순하게 생각하면

A 선택
A 안 선택

B 선택
B 안 선택

C 선택
C 안 선택
...

이런 식으로 모든 조합을 확인할 수도 있다. 이렇게 하면 N이 최대 500이니까 2^500이므로 시간복잡도를 통과할 수 없다. 

그렇다면, "모든 경우를 보지 않고, 매 순간 좋은 선택 하나만 고르고 넘어가도 될까?"
라고 생각하면서 그리디를 떠올릴 수 있다. 

 

 

 

3. 지금 어떤 회의를 선택하는게 좋지?

처음에 여러 기준을 떠올릴 수 있다. 

- 가장 짧은 회의? -> 짧아도 여러 회의와 시간이 겹치면 최대가 안될 수 있다. 

- 시작 시간이 가장 빠른 회의? -> 1~100 동안 회의를 진행하면 최대가 안될 수 있다. 

- 가장 빨리 끝나는 회의? -> 가장 빨리 끝나는 회의는 회의 시간이 짧은 것도 포함하고 있고, 이후 다음 선택의 기회를 많이 남겨놓은 선택이다. 

 

 

 

4. 그리디 선택

지금까지 "가장 빨리 끝나는 회의를 선택하면, 이후 선택할 수 있는 시간이 가장 많이 남는다" 는 결론으로 

매 순간 현재 상황에서 가장 좋은 선택을 하는 그리디 알고리즘으로 후보를 좁혔다. 

단, 현재 선택이 가장 좋은 최선의 선택임을 확정하는 edge case들도 생각해 보아야 한다. 

- 가장 빨리 끝나는 회의를 골랐는데 손해 보는 경우가 있는지? 

- 가장 빨리 끝나는 회의를 골랐는데 다른 선택을 했을 때보다 최소가 되는 경우가 있는지? 

 

 

사고 방식 정리

회의를 최대한 많이 선택해야 한다.
        ↓
모든 조합을 보면 너무 많다.
        ↓
하나씩 선택하면서 최적해를 만들 수 없을까?
        ↓
그렇다면 지금 어떤 회의를 선택해야 하지?
        ↓
짧은 회의? 시작이 가장 빠른 회의? 끝이 가장 빠른 회의?
        ↓
빨리 끝날수록 다음 회의를 선택할 기회가 많다.
        ↓
현재 선택이 미래의 선택을 가장 많이 남긴다.
        ↓
그리디 알고리즘 확정