[백준] 1931 파이썬(python) : 회의실 배정 - (★)

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

1931번: 회의실 배정

 

 

import sys
n = int(sys.stdin.readline())
meeting = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ] #1
meeting.sort(key=lambda x : (x[1], x[0])) #2
res, endTime = 0, 0 #3
for i in range(len(meeting)):
    if endTime <= meeting[i][0]: #4
        endTime = meeting[i][1]
        res += 1
print(res)

 

정렬을 추가한 그리디 문제이다. 그리디 문제는 아직 낯설어서 접근법이 어렵지만 설명해 보고자 한다.

여러 가지의 회의 시작시간과 종료시간이 있다. 그중 가장 많은 회의를 하려면 어떻게 해야 할까? 회의시간이 짧은 것들을 최대한 많이 넣으면 된다. 그러면 "종료시간 - 시작시간"을 구해서 카운트를 추가해주면 되는 걸까? 그렇지 않다. 끝나는 시간과 같거나 더 큰 수를 시작시간으로 가진 회의를 선택해야 하기 때문이다.

 

그래서 끝나는 시간이 가장 빠른것 기준으로 정렬하고 끝나는 시간이 같다면 시작시간이 적은 순서대로 오도록 정렬한다.

 

끝나는 시간이 먼저오도록 하는 이유는 시작시간은 빠른데 끝나는 시간은 늦은 회의를 오래 하는 경우가 존재하기 때문이다. 

 

#1 : 튜플로 시작시간과 종료시간을 입력받음

#2 : 종료시간 오름차순, 시작시간 오름차순으로 정렬

#3, 4 : 첫 endTime을 0으로 지정하고 종료시간이 적은대로 정렬했으니 조건문에서 가장 많은 회의 수를 고를 수 있다.

 

11000번 문제 강의실 배정이랑 이름이 비슷하다.(https://hgk5722.tistory.com/281)