1931 - 회의실 배정

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

1931번: 회의실 배정

 

- Greedy

 

import sys
input = sys.stdin.readline

n = int(input())
meetTime = list()
for _ in range(n):
    meetTime.append(list(map(int, input().split())))

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

lastTime, cnt = meetTime[0][1], 1
for i in range(1, n):
    if lastTime <= meetTime[i][0]:
        cnt += 1
        lastTime = meetTime[i][1]

print(cnt)

 

디미고에서 자료구조 시간에 배웠던 그리디 유형이라 접근은 쉽게 했다!

 

근데 수업을 대충 들어서인지 에러가 함 나서 ㅎ;

sort 할 때 종료 시간만을 기준으로 잡으면,

2
1 1
0 1

같은 테스트케이스가 들어갔을 때 output이 1이 나와버린다

 

그래서 종료 시간을 1순위, 시작 시간을 2순위로 정렬해줘야 완벽한 답이 나온다.

 

 

파이썬 sort 함수는 신이 맞다