[백준 1931] 회의실 배정 - Python (그리디 알고리즘, 정렬)

 

1931번: 회의실배정

 

<내 코드>

 

N = int(input())

times = [list(map(int, input().split())) for _ in range(N)]
times.sort(key=lambda x: (x[1], x[0])) # 끝 시간으로 정렬 후, 시작 시간으로 정렬

cnt = 1
end_time = times[0][1]
for i in range(1, N):
    if times[i][0] >= end_time: # 앞 요소의 끝 시간보다 현재 요소의 시작시간이 크거나 같을 때
        cnt += 1
        end_time = times[i][1]

print(cnt)

 

문제에서 제약조건이 다음과 같이 주어졌다.

- 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

- 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

최대한 많은 회의를 잡기 위해서는 끝나는 시간이 짧아야 한다. 회의가 빨리 끝나야 다음 회의를 시작할 수 있다. 

그래서 우선 끝나는 시간으로 정렬한다. 여기서 중요한 것이 시작 시간과 끝나는 시간이 같은 케이스다.

예를 들어 (2,2) 와 (1,2) 있을 때 끝나는 시간으로 정렬을 한다면 (2,2)가 먼저 정렬되고 (1,2)가 무시된다. 그래서 시작과 끝 시간이 같은 경우는 시작 시간 기준으로 다시 정렬을 해줘야 한다.