백준 / 1931번 / 회의실 배정 / python 파이썬

 

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

 

 

 

처음 문제를 보자마자 알고리즘 강의 때 배운 Interval Schduling의 접근법이 생각났다. Earliest finish time을 기준으로 접근하여 가장 빨리 끝나는 것을 선택하면 최적의 답을 구할 수 있는 것이다.

 

 

이를 고려하여 입력 받은 회의 시간들을 끝나는 시간을 기준으로 오름차순 정렬하고 제출하였는데 실패하였다. 

그 이유는 끝나는 시간이 동일한 회의들에 대한 처리를 해주지 않았기 때문이었다. 따라서 아래와 같이 

1. 회의가 끝나는 시간 2. 회의 시작 시간  이렇게 우선 순위를 두어서  .sort(key = lambda x: x[1])이 아닌  .sort(key = lambda x: (x[1], x[0])) 로 정렬하여 count하면 답을 구할 수 있다.

 

 

코드 

import sys
input = sys.stdin.readline

n = int(input())
time_intv = []

for i in range(n):
    time_intv.append(list(map(int, input().split())))

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

end = time_intv[0][1]
for i in range(1, n):
    if time_intv[i][0] >= end:
        count += 1
        end = time_intv[i][1]
print(count)