[백준] 1931번: 회의실 배정 - python

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

1931번: 회의실 배정

 

최대한 방을 사용할 수 있게 정렬하는 문제

 

일단 끝나는 순으로 정렬을 한다.

그 이유는 아무리 일찍하더라도 죽치고 사용하면 배정할때 후순위로 밀리기 때문에 일단 가장 일찍 끝나는 순으로 정렬을 한다.

그 후 순서대로 비교하면서 끝나는 시간과 그 다음 타임의 시작하는 시간이 같거나 크면 사용이 가능하므로 tmp라는 빈공간을 생성해 그 값을 계속 저장하면서 갯수를 증가시켜준다. 그러면 최대한 많이 사용하는 경우의 수가 나오게 된다.

 

n = int(input())

arr = []
for i in range(n):
    start , end= map(int , input().split())
    arr.append((start, end))

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

tmp = 0
cnt = 0
for start, end in arr:
    if tmp <= start:
        tmp = end
        cnt+=1
print(cnt)

 

완성