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

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

1931번: 회의실 배정

---

1. 접근 방식

• 회의 시작 시간과 끝나는 시간이라는 2가지 기준으로 오름차순 정렬하자.

정렬하기

앞 타임 회의가 끝나면 이후 타임 회의가 시작될 수 있기 때문에 우선 시간을 기준으로 정렬해준다.

 

 

• 현재 회의 시작 시간이 이전 회의의 끝나는 시간보다 크거나 같을 때, 현재 회의를 시작할 수 있다.

이전 회의가 끝나는 시간이 end이고 현재 회의 시작 시간이 x일 때, 현재 회의 시작 조건을 코드로 나타내면 if x >= end이다. 현재 회의가 새롭게 시작되었으므로, 회의 개수는 + 1된다.

 

 

 

• 현재 회의가 이전 회의 시간이 끝나는 시간보다 일찍 시작하고, 일찍 끝난다면 현재 회의가 회의 최대 개수를 확률이 높다.

현재 회의 시작 시간이 x, 끝나는 시간이 y일 때 조건을 코드로 나타내면 if x < end and y < end이다.

기존에 카운트했던 회의 정보 대신 현재 회의 (x, y)를 진행하는 것이 이후 더 많은 회의를 진행할 가능성이 있다. 이전 회의보다 현재 회의가 더 빨리 회의가 끝나기 때문이다.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline

n = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(n)]
meetings.sort()

start, end = meetings[0]
count = 1
for x, y in meetings[1:]:
    if x < end and y < end:
        start, end = x, y

    elif x >= end:
        start, end = x, y
        count += 1

print(count)