백준 1931번: 회의실 배정

문제

• https://www.acmicpc.net/problem/1931
• 시작 시간과 끝 시간이 있는 아이템들이 주어질 때, 양립 가능한 최대 개수의 조합 찾기

기록 포인트

• 그리디 알고리즘 절차
  • 아이템 선택 규칙에 따라 하나의 아이템 i을 선택한다.
  • 아이템 i와 양립 불가능한 다른 아이템들을 전부 제거한다.
  • 모든 아이템들이 처리될 때까지 동일 절차를 반복한다.

접근 방식

• 1단계: 아이템 정렬
  • 종료 시간(f) 순으로 정렬
  • 종료 시간(f)이 동일할 경우, 시작 시간(s) 순으로 정렬
    • 종료 시간이 동일한 아이템은 시간 시간이 짧은 것이 먼저 처리되어야 함
    • 가령, 두 아이템 i(4, 4), j(2, 4)를 보면
      • i가 먼저 처리된 경우, f(j) < s(i) 이므로 j는 양립 불가
      • j가 먼저 처리된 경우, f(i) >= s(j) 이므로 j도 양립 가능
• 2단계: 그리디 알고리즘 실행
  • 남은 아이템 중 종료 시간이 가장 빠른 아이템(i)을 선택
  • 선택된 아이템과 양립 불가능한 아이템 제거
    • 즉 시작 시간이 선택된 아이템의 종료 시간보다 빠른 아이템 제거
  • 모든 아이템이 처리될 때까지 동일 절차 반복

제출 답안

import sys

N = int(sys.stdin.readline())
teams = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 1단계: 종료 시간 순으로 정렬
# - 종료 시간이 동일한 경우, 시작 시간 순으로 정렬
teams.sort(key=lambda t: (t[1], t[0]))

# 2단계: 기준에 맞게 하나씩 선택
# - 1) 종료 시간이 가장 빠른 팀 선택
# - 2) 선택된 팀과 양립 불가능한 팀 제거
# - 3) 남은 팀이 있을 때까지 1,2 절차 반복

selected = []
i = -1
last_finish_time = 0
while i < len(teams)-1:
    i += 1
    team = teams[i]
    ts, tf = team
    # 남은 팀들 중 시작 시간이 선택된 마지막 팀의 종료 시간보다 빠른 팀 제외
    if ts < last_finish_time:
        continue 
    # 종료 시간이 가장 빠른 팀을 선택
    # (종료 시간 순으로 정렬되어 있으므로 가장 앞에 있는 팀)
    last_finish_time = tf
    selected.append(team)

print(selected)
print(len(selected))