(파이썬) 백준 1931번 "회의실 배정"

---

# 원리

 

종료 시간이 제일 빠른 회의부터 차례대로 고르면 됩니다.

 

만일 종료 시간이 동일한 회의가 여러 개라면, 그 중 아무거나 골라도 됩니다.

종료 시간이 동일하다면 회의 시간이 필연적으로 겹치기 때문입니다.

단, 종료 시간과 시작 시간이 동일한(회의 시간이 0인) 회의는 예외입니다.

 

 

예를 들어 시작 시간과 종료 시간이 아래와 같은 회의 4개가 있다고 가정해봅시다.

회의	시작 시간	종료 시간
A	7	10
B	8	10
C	9	10
D	10	10

종료 시간이 동일한 회의 A, B, C 중에서는 그 어느 회의를 골라도 상관이 없습니다.

회의 D 또한 회의 A, B, C와 종료 시간이 동일하지만, D는 시작 시간과 종료 시간이 동일하기 때문에 예외로 생각해야합니다.

회의 A, B, C 중 하나가 끝나고 나면 회의 D를 연달아 시작할 수 있기 때문입니다.

 

 

회의 시간을 리스트에 담은 뒤 종료 시간을 기준으로 오름차순 정렬하고, 종료 시간이 같은 회의끼리는 시작 시간을 기준으로 오름차순 정렬하면 되겠습니다. 그러면 자동으로 종료 시간이 동일한 회의들 중에서는 '시작 시간과 종료 시간이 동일한 회의'가 제일 마지막에 위치하기 때문입니다.

 

 

 

 

---

# 답

import sys

input = sys.stdin.readline
meeting = [tuple(map(int, input().split())) for _ in range(int(input()))]

meeting.sort(key=lambda x: (x[1], x[0]))
ans = 0
pre = 0
for s, e in meeting:
    if pre <= s:
        pre = e
        ans += 1

print(ans)