[백준/Python] 1931번: 회의실 배정

📁 문제

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

---

💭 풀이

① 한 개의 회의실이 있음
② 이를 사용하고자 하는 N개의 회의에 대해 회의실 사용표 만들려고 함
③ 각 회의 I에 대해 시작시간과 끝나는 시간 주어져있음

📍 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기

❗ 단,
회의는 중단 X, 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음
회의의 시작시간 = 끝나는 시간 → 시작하자마자 끝남

---

🍰 알고리즘

1) 리스트에 회의의 시작시간과 끝나는 시간 저장

2) 끝 시간 기준으로 먼저 정렬
👉 빨리 끝날 수록 더 많은 회의를 진행할 수 있음

3) 그 다음 시작시간 기준으로 정렬
👉 앞 회의가 끝나고 최대한 빨리 시작할 수록 시간 낭비 줄어듦

4) 앞 회의의 끝나는 시간보다 현재 회의의 시작시간이 늦으면 회의수 1 증가

---

💡 sort, sorted 함수에 있는 속성 값을 이용해 정렬할 수 있음

sorted(time, key=lambda x: (x[1], x[0]))

참고 https://cigiko.cafe24.com/python-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-sort%EC%99%80-sorted/

---

🤍 코드

time = []
for i in range(int(input())):
  start, end = map(int, input().split())
  time.append((start, end))

# 끝 시간 기준으로 먼저 정렬 후, 시작시간 기준으로 정렬
time = sorted(time, key=lambda x: (x[1], x[0]))

before_end = 0
meeting = 0
for t in time:
  start, end = t[0], t[1]

  if before_end <= start:
    meeting += 1
    before_end = end

print(meeting)