그리디: 백준 1931 파이썬 회의실 배정

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

1931번: 회의실 배정

 

풀이:

이 문제는 정렬을 해야 한다는 아이디어를 생각해내면 풀 수 있는 문제이다. 

sort()함수의 key값을 사용해 회의실 사용이 끝나는 시간을 기준으로 먼저 정렬하고 끝나는 시간이 같다면

시작시간을 기준으로 정렬되게 한다.

 

그리고 회의실 사용이 끝나는 시간과 다른 회의의 시작시간을 비교해 카운트를 하면 된다.

 

정답:

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

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

start = arr[0][0]
end = arr[0][1]
cnt = 1

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

print(cnt)