[BOJ] 1931 회의실 배정 Python

 

그리디 알고리즘, 정렬 문제이다

 

정답 풀이법은 다음과 같다.

1) 끝나는 시간이 빠른 순서대로, 그 다음은 시작하는 시간이 빠른 순서대로 정렬한다.

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

2) 이후 배열 길이만큼 반복문 돌면서 앞선 x[1] 값보다 뒤 y[0]값이 크거나 같으면

answer += 1

endtime = y[1]

해주면 된다!

 

*** 배열은 되도록이면 append 하지 말고 미리 크기 만큼 선언, 초기화해놓고 값을 변경해주자

 

T = int(input())

mt = [[0,0] for _ in range(T)]

for i in range(T):
    a, b = map(int, input().split())
    mt[i][0] = a
    mt[i][1] = b

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

answer = 1
endtime = mt[0][1]
for i in range(1, T):
    if mt[i][0] >= endtime:
        answer += 1
        endtime = mt[i][1]
print(answer)

 

참고

[백준알고리즘] 1931번: 회의실배정 -Python