📌 문제 요약

• 문제 이름: 1931번: 회의실 배정
• 알고리즘 분류: 그리디 알고리즘 (Greedy), 정렬
• 사용 언어: Python 3

1개의 회의실을 사용하고자 하는 $N$개의 회의에 대하여 회의실 사용표를 만드려 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아야 한다.

💡 문제 접근 방법 (핵심 로직)

이 문제는 전형적인 그리디(탐욕) 알고리즘 문제입니다. 처음에는 '시작 시간'이 빠른 순서대로 배정해야 하나 고민했지만, 회의가 일찍 시작하더라도 엄청나게 늦게 끝난다면 그 뒤의 회의들을 하나도 진행할 수 없게 됩니다.

따라서 가장 많은 회의를 배정하기 위한 최적의 기준은 '회의가 끝나는 시간'이 되어야 합니다.

1. 회의 정보를 (시작 시간, 종료 시간) 형태로 리스트에 입력받습니다.
2. 리스트를 정렬할 때, ① 종료 시간을 기준으로 오름차순 정렬하고, 만약 종료 시간이 같다면 ② 시작 시간을 기준으로 오름차순 정렬합니다.
3. 정렬된 회의들을 순회하며, 현재 회의의 시작 시간이 '직전 회의의 종료 시간'보다 크거나 같다면 회의를 배정(카운트 +1)합니다.

💻 코드 구현

import sys
input = sys.stdin.readline

n = int(input())
meetings = []

for _ in range(n):
    start, end = map(int, input().split())
    meetings.append((start, end))

# 1. 끝나는 시간 기준으로 오름차순 정렬
# 2. 끝나는 시간이 같다면 시작 시간 기준으로 오름차순 정렬
meetings.sort(key=lambda x: (x[1], x[0]))

count = 0
last_end_time = 0

for start, end in meetings:
    # 현재 회의의 시작 시간이 직전 회의의 종료 시간 이상일 때만 회의 배정 가능
    if start >= last_end_time:
        count += 1
        last_end_time = end

print(count)