활동 선택, 스케쥴링 문제 (그리디)

활동 선택, 스케쥴링 문제 (그리디)

쉬운 유형의 문제로 코딩테스트에서 자주 본 적 있다.

백준 1931 참고

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

# 회의 시작 시간, 회의 끝나는 시간
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
# 여러 회의 시간이 주어진다.
# 최대한 많은 회의를 하려면 ?

그림을 보면 해당 예제는 최대 4번의 회의를 할 수 있다.

---

그리디 알고리즘은 매 순간 마다의 최적의 선택을 하는 알고리즘 설계법이다.

하지만 매 순간 최적의 선택을 한다고 해서, 최종적으로 결과가 최적을 보장하지는 않기에, 문제를 잘 읽어 보아야 한다.

즉, 지금 현재 가장 좋아 보이는 것을 계속 선택해도 최적의 해가 되는가를 검토해봐야 한다.

이러한 스케쥴링 문제는 직관적으로 생각해보아도 그리디 알고리즘으로 설계가 가능하다는 것을 알 수 있다.

그냥 수업(회의)이 빨리 끝나면 다음 수업을 빨리할 수 있고, 그 다음 수업도 최대한 일찍 끝나야 또 다음 수업을 빨리 할 수 있기 때문이다.

이런 식으로 매번 빨리 끝나는 회의를 선택하여 코드를 짜면 된다.

---

파이썬 코드

import sys

N = int(sys.stdin.readline())
times = []
for n in range(N) :
    times.append(list(map(int, sys.stdin.readline().split())))

# 일찍 끝나는 순서로 정렬

times.sort()
# 같은 end time 내에서
# 빠른 start time 순으로 정렬 되어있어야 한다.
# [[4, 4], [3, 4], [2, 4]] 의 경우 [4, 4] 만하고 끝나버리기 때문
times.sort(key = lambda x : x[1])

answer = 0
end = 0

for t in times :
    if t[0] >= end : # 회의 시간 겹치지 않기 위해..
        answer += 1
        end = t[1]

print(answer)

-dnlxo