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

📌문제 출처

백준 단계별 문제풀이 - 그리디 알고리즘
https://www.acmicpc.net/problem/1931

❓ 문제

 

❗ 풀이

• 그리디 알고리즘 + list 정렬

📗 풀이 코드

import sys
input = sys.stdin.readline
# 1차로 시작 시간 순으로 정렬
meetings = sorted([list(map(int,input().split())) for _ in range(int(input()))])
# 2차로 종료 시간 순으로 정렬
meetings.sort(key=lambda x : x[1])
# 회의 개수와 최종 회의 종료 시간
cnt = last = 0
for sta,end in meetings:
    if last <= sta : # 최종 회의 시간 종료 이후 다음 회의가 시작이라면
        cnt += 1 # 회의가 가능하므로 +1
        last = end # 최종 회의 종료 시간 초기화
print(cnt)

📗 코드 해설

• 1차로 시작 시간 순, 2차로 종료 시간 순으로 정렬
• 더 빨리 시작하고, 더 빨리 마치는 미팅 순으로 정렬되어있기에,
  리스트에서 미팅을 하나씩 불러와서 해당 미팅을 진행할 수 있는지를 판단하면 된다.
• 이미 해당 미팅보다 빨리 시작하고 빨리 끝나는 미팅은 고려를 완료했기에 해당 미팅 진행 가능 여부만 판단하면
  최대 미팅 회수를 고려할 수 있음