[Python/Baekjoon] 1931. 회의실 배정

정나린·2022년 10월 16일

greedy python 그리디 백준

💬 문제

문제 난이도: 백준 실버 1

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

❗️접근 방법

최대한 많은 회의를 열 수 있도록 스케쥴을 짜야 한다.
입력으로 시작시간과 끝시간이 같은(즉, 시작하자마자 끝나는) 회의가 주어질 수 있다.
따라서 시작하는 시간 또는 끝나는 시간 하나만 가지고서 정렬하면 위의 케이스가 반례로 작용한다.
예를 들어
끝나는 시간 단일 기준으로 오름차순을 한다면
(1, 2) -> (5, 5) -> (3, 5) 으로 정렬될 수도 있고
(1, 2) -> (3, 5) -> (5, 5) 으로 정렬될 수도 있다. (입력 순서에 따라서 달라질 것)
위의 케이스는 (1, 2), (5, 5) 단 2개의 회의가 열릴 수 있겠지만
아래의 케이스는 (1, 2), (3, 5), (5, 5)로 3개 모두 열릴 수 있다.
따라서 2개 이상의 회의가 같은 끝 시간을 가질 때 먼저 시작하는 것부터 추가해줘야하므로
끝나는 시간 -> 시작하는 시간 순으로 2가지 기준으로 오름차순 정렬해줘야 한다.

✅ 정답 코드(시작하는 시간->끝나는 시간 순서로 오름차순 정렬)

# 회의실 배정
import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
meetings = []
for _ in range(N):
    meetings.append(tuple(map(int, input().split(' '))))
    
meetings.sort(key=lambda x:(x[0], x[1]))

time = meetings[-1][1]
cnt = 0
for meeting in meetings[::-1]:
    if meeting[1] <= time:
        time = meeting[0]
        cnt += 1
print(f'{cnt}')

뒤에서부터 회의를 추가해 나감.

✅ 정답 코드(끝나는 시간->시작하는 시간 순서로 오름차순 정렬)

# 회의실 배정
import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
meetings = []
for _ in range(N):
    meetings.append(tuple(map(int, input().split(' '))))

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

time = meetings[0][0]
cnt = 0
for meeting in meetings:
    if meeting[0] >= time:
        time = meeting[1]
        cnt += 1
print(f'{cnt}')