문제 분석
전에 몇 번 본거같은 문제 유형인데 볼 때마다 틀린 풀이로만 생각하는것 같다.
이 문제를 간단하게 바꾸면 수직선에 시작위치와 끝 위치가 주어진 선분을 겹치지 않게 최대한 많이 배치하는 것으로 바꿀 수 있다.
Key idea
내가 문제를 풀 때에는 가장 길이가 짧은 선분부터 수직선 위에 배치하면 최대가 나올 수 있을 거라고 생각했다. 그런데 전에도 이렇게 생각하다가 문제를 틀렸던 것 같아서 다른 방법을 고민해보다가 결국 다른 사람의 풀이에서 힌트를 얻었다.
그리디 알고리즘은 현재 상태에서 최선의 선택을 반복하다보면 최적해를 찾을 수 있는 알고리즘이다. 따라서 이 문제에서 한 선분을 선택했을 때 가장 많은 선분을 배치하는 방법을 생각해보면 선분이 최대한 빨리 끝날 때 다음 위치에 올 수 있는 선분의 가짓수가 가장 많을 것이다.
이 생각이 내 방식과 다른 점은 나는 선분의 길이가 짧은 순서로 정렬하기 때문에 뒤쪽 선분이 먼저 수직선에 배치되면 최적해를 이루는 앞쪽 선분이 선택되지 못할 가능성이 있다. 하지만 후자의 방법은 선분을 앞에서부터 채워나가기 때문에 그런 상황이 발생하지 않는다.
Solution
위에서 말한대로 각 스케줄(선분)을 종료시간이 빠른 순서로 정렬하고, 종료시간이 같은 스케줄끼리는 시작시간이 더 빠른 스케줄을 먼저 확인하도록 정렬한 다음 리스트를 순회하면서 스케줄을 선택하면 최적해를 얻을 수 있다.
n = int(sys.stdin.readline())
schedule = []
for i in range(n):
s, e = map(int, sys.stdin.readline().strip().split(' '))
schedule.append((s, e))
schedule.sort(key=lambda x: (x[1], x[0]))
count = 0
now = 0
for time in schedule:
start, end = time
if start >= now:
count += 1
now = end
print(count)