백준 1931번: 회의실 배정 (파이썬)

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

1931번: 회의실 배정

 

문제

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

 

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

 

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

풀이

 

이 문제 역시 그리디 알고리즘으로 쉽게 해결할 수 있다.

현재 가능한 회의 중 끝나는 시간이 가장 빠른 회의를 우선으로 진행하도록 한다.

이때 끝나는 시간이 같은 회의라면 시작 시간이 빠른 회의를 선택하도록 한다.

즉 끝나는 시간에 대해 오름차순 정렬을 한 뒤, 만약 끝나는 시간이 같은 경우에는 시작 시간에 대해 오름차순 정렬을 해야한다.

이를 위해 리스트 내장 함수인 sort를 사용하였고, key 값으로 lambda x : (x[1], x[0])을 주었다.

 

이후 현재 시간을 0으로 초기화한 뒤, 가능한 회의 중 끝나는 시간이 가장 빠른 회의를 선택하며 개수를 세어 준다.

해당 회의를 선택한 뒤에는 현재 시간을 회의가 끝나는 시간으로 변경해 주어야 한다.

 

소스 코드

 

n = int(input())

inputs = []
for i in range(n):
    start, end = input().split()
    start, end = int(start), int(end)
    inputs.append((start, end))
inputs.sort(key = lambda x : (x[1], x[0]))

now = 0
cnt = 0
for i in range(n):
    if now <= inputs[i][0]:
        now = inputs[i][1]
        cnt += 1
print(cnt)