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

Python

[Python] 백준 알고리즘 온라인 저지 1931 회의실 배정

1931 회의실 배정

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

1931번: 회의실 배정

알고리즘 분류

• 정렬
• 그리디 알고리즘

알고리즘 분류와 같이 미리 정렬을 하고 풀이하는 것이 이 문제의 핵심이었다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
m = []
for _ in range(n):
    a, b = map(int, input().split())
    m.append([a, b])

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

cnt = 1
end_m = m[0][1]
for i in range(1, n):
    if m[i][0] >= end_m:
        cnt += 1
        end_m = m[i][1]
print(cnt)

---

풀이

인풋을 받고 리스트 m을 끝나는 시간의 오름차순으로 정렬한 뒤, 시작하는 시간의 오름차순으로 정렬한다.

최대 개수를 받는 문제인 만큼 빨리 끝나는 회의들을 여러 개 선택하는 것이 더 많은 회의를 받을 수 있기 때문이다.

이후에는 cnt를 1로 선언하고 맨 처음 시작되는 회의의 끝나는 시간을 end_m에 저장해놓는다.

for문을 1부터 시작하여 미리 저장해놓은 수와 다른 수들을 비교하며 cnt를 하나씩 늘리고 end_m을 새로 선언한다.

---

풀이 결과

1913 풀이결과