[BOJ 1931] 회의실 배정 (Python 3)

www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

N=int(input())
array=[]
count=1
for i in range(N):
    start, end=map(int, input().split())
    array.append((start,end))
 
array.sort(key=lambda x: (x[1], x[0]))
meeting=array[0]
 
for i in range(1,len(array)):
    if meeting[1]<=array[i][0]:
        count+=1
        meeting=array[i]
print(count)

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

이 문제의 핵심은 종료시간이 가장 짧은 것을 계속해서 고르고 count 값을 올리는 것이다. (종료시간이 짧은 것을 골라야 최대한 많은 회의를 열 수 있다.)

1. 종료시간이 빠른 순으로 정렬한다. (정렬할 때 종료 시간이 같다면 시작 시간이 먼 순서대로 정렬한다. <- 이 부분을 체크하지 못해서 틀렸었다. )

2. 정렬된 배열에서 end 시간<=시작 시간일 때의 경우만 골라서 count 값을 올려준다.

 

그리디 알고리즘은 "어떤 것을 고를 것인가?"의 기준을 정하는게 중요한것 같다.