1. 문제 설명

회의실 배정

2. 문제 분석

끝나는 시간을 빠른 순서대로 주어진 회의를 정렬해, 지금 끝나는 시점에서 선택 가능한 회의를 하나씩 골라간다.

1. 가장 많은 회의를 고르기 위해서는 끝나는 시간이 빠른 순서대로 회의를 정렬한다. 끝나는 시간이 같다면, 시작하는 시간이 빠른 순서대로 고르자.
2. 순서대로 회의를 확인하면서, 지금 택한 회의 종료 시점을 기준으로 고를 수 있는 회의가 있다면 선택하자.

이 문제에서 끝나는 시점과 동시에 시작할 수 있기 때문에 end <= new_start일 때 주어진 회의를 선택할 수 있다.

이 시점에서 회의를 하나 더 할 수 있기 때문에 cnt += 1, 그리고 다음 회의를 추가할 때 기준으로 삼을 회의 종료 시간은 이 새로운 회의의 new_end이므로 end = new_end가 된다.

• 그리디 알고리즘을 풀기 위해서는 문제 풀이 기준에 대한 간단한 원칙을 만들어야 한다는 데 주의하자. end <= new_start와 같은 문제에서 제시한 사소한 기준을 체크하자.

3. 나의 풀이

n = int(input())
times = []
for _ in range(n):
    start, end = map(int, input().split())
    times.append([start, end])
times.sort(key=lambda x:(x[1], x[0]))
# 회의가 빨리 끝나는 순서대로 정렬하자. 끝나는 시간이 같다면 빨리 시작하는 순서대로 고른다.
start, end = -1, -1
cnt = 0

for time in times:
    new_start, new_end = time
    # 지금 끝난 시점에서 시작 가능한 회의라면 고를 수 있다.
    if end <= new_start:
        end = new_end
        # 회의가 끝나는 기준은 이 새로 택한 회의가 마치는 시간이 된다.
        cnt += 1

print(cnt)