[그리디] 회의실 배정

🔹 문제 설명

한 개의 회의실에서 여러 개의 회의를 예약하려고 합니다.
각 회의는 시작 시간과 종료 시간이 주어지며, 한 번에 하나의 회의만 진행할 수 있습니다.
최대한 많은 회의를 진행하려면, 회의를 어떻게 선택해야 할까요?

 

🔹 입력 형식

• 첫 번째 줄에 **회의의 개수 N**이 주어집니다. (1 ≤ N ≤ 100,000)
• 이후 N개의 줄에는 **각 회의의 시작 시간과 종료 시간 (start, end)**이 주어집니다.
  (0 ≤ start < end ≤ 2^31 - 1)

🔹 출력 형식

• 최대 사용할 수 있는 회의의 개수를 출력합니다.

🔹 예제 입력

 

5
1 4
2 3
3 5
0 6
5 7

🔹 예제 출력

3

✅ 최적의 선택:

• (2, 3) → (3, 5) → (5, 7) (총 3개의 회의 진행 가능)

 

---

💡 개념

그리디(Greedy) 알고리즘은 현재 상황에서 가장 좋은 선택(최적의 선택)을 반복적으로 수행하여 최적해를 구하는 알고리즘입니다.

즉, "매 순간마다 최적이라고 생각되는 선택을 하면, 결국 전체적으로도 최적의 해가 된다!" 라는 아이디어를 기반으로 합니다.

 

📌 해결 방법 (그리디 알고리즘)

💡 핵심 아이디어: "빨리 끝나는 회의부터 선택"하면 최적의 해를 구할 수 있다!

1. 회의가 종료 시간이 빠른 순서대로 정렬해야 함.
   • 일찍 끝나는 회의를 먼저 선택하면, 이후 더 많은 회의를 진행할 수 있음.
   • 만약 종료 시간이 같다면 시작 시간이 빠른 순서대로 정렬.
2. 정렬된 회의 리스트에서 현재 회의의 종료 시간 이후에 시작하는 회의들을 차례로 선택.

 

✅ 코드 구현

import sys

input = sys.stdin.readline

# 입력 받기
n = int(input().strip())
meetings = [tuple(map(int, input().split())) for _ in range(n)]

# 종료 시간 기준으로 정렬 (종료 시간이 같으면 시작 시간 기준 정렬)
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)  # 최대 회의 개수 출력