[백준/파이썬Python] #1931 회의실 배정: 그리디는 어떤 기준을 세울지 생각하자 🤝

🤝 문제

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

한 개의 회의실이 있고, N개의 회의에 대하여 회의실 사용표를 만드려고 함
회의 시간이 겹치면 안됨
회의의 시작시간과 끝나는 시간이 같을 수도 있음
회의의 최대 개수 찾기

🧠 접근 방법

• 회의 시간이 짧은 것을 기준으로 해야 최대한 많은 회의를 잡을 수 있을 것 같다.
  → 회의의 스케줄링(겹치는 것)까지 고려해야 한다.
  → 첫번째 회의만 잘 정하면 된다.
  → 가장 처음에 빨리 끝나는 회의가 결국에는 처음에 가장 짧은 회의이다.

입력

• N: 회의의 수
• ~N+1: 회의의 정보(회의 시작시간, 끝나는 시간)

출력

• 최대 사용할 수 있는 회의의 최대 개수

👩🏻‍💻 코드

📑 전체 코드

1차

import sys

N = int(sys.stdin.readline())
meetings = []
for _ in range(N):
    meetings.append(list(map(int, sys.stdin.readline().split())))

meetings.sort()
meetings.sort(key=lambda x:x[1])

timetable = [meetings[0]]
for i in range(1, len(meetings)):
    now = meetings[i]
    if timetable[-1][1] <= now[0]:
        timetable.append(meetings[i])

print(len(timetable))

2차(개선)

import sys
N = int(sys.stdin.readline())
meetings = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
meetings = sorted(meetings, key=lambda x: (x[1], x[0]))

table = []
table.append(meetings[0])
if N > 1:
    for i in range(1, N):
        if meetings[i][0] >= table[-1][1]:
            table.append(meetings[i])

print(len(table))

• 회의 정보를 입력받는 과정 단순화
• lambda 다중 조건으로 한 번에 정렬
• now라는 새로운 변수 없이 타임테이블에 저장한 마지막 회의 바로 사용