백준 1931번 파이썬 문제풀이(회의실 배정)

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

1946번: 신입 사원

---

유명한 웰노운 그리디 문제이다. 

 

풀이방법은 굉장히 간단하다. 끝나는 시간을 오름차순으로 정렬해서 빨리끝나는 것들만 계속 선택하면 된다.

 

단! 시작시간도 고려해야 하기 때문에 끝나는시간을 오름차순으로 정렬하되, 끝나는 시간이 같을 경우 시작시간을 기준으로도 오름차순을 해주어 빨리 시작하는 것을 선택해주게끔 해야한다.

 

* 그이유는...

(시작하자 말자 끝나는 회의가 존재하기 때문이다.

5
6 7
6 6
5 6
5 5
7 7

만약 시작시간을 기준으로 정렬은 안해준다면 다음 반례를 통과하지 못한다.

)

 

import sys

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

arr.sort(key=lambda x: (x[1], x[0]))

cnt = 1
obj = arr[0][1]
for i in range(1, N):

    if obj <= arr[i][0]:
        obj = arr[i][1]
        cnt += 1

print(cnt)