백준 1931 회의실 배정

문제

---

솔루션

import sys
input= sys.stdin.readline
N = int(input())
li = []

for i in range(N):
    start, end = map(int,input().split())
    li.append((start, end))

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

count = 1
end = li[0][1]

for i in range(1, N):
    if li[i][0]>=end:
        end = li[i][1]
        count += 1

print(count)

---

깨달은점

어디서 많이 본거같다 했는데 전공시간에 본 예제였다.

회의시간배정문제로 그리디를 이용해서 풀면 된다.

 

for i in range(N):
    start, end = map(int,input().split())
    li.append((start, end))

튜플 형태로 각 회의의 시작시간과 끝나는시간을 리스트에 넣어 저장한다.

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

종료 시간이 빠른 회의를 먼저 배정해야 더 많은 회의를 배정할수 있기 때문에 종료시간(x[1])이 빠른 순으로 먼저 정렬한 후, 끝나는 시간이 같은 경우에는 시작시간이 빠른경우로 정렬한다. 

count = 1
end = li[0][1]

for i in range(1, N):
    if li[i][0]>=end:
        end = li[i][1]
        count += 1

 

첫 번째 회의는 항상 선택하므로 count는 1로 설정하고, 첫 번째 회의의 종료 시간을 end로 설정한다.

현재 회의의 시작 시간 li[i][0]이 이전 회의의 종료 시간 end 이상인 경우, 종료 시간을 end에 업데이트하고, count를 증가시킨다.