[BOJ] 1931번: 회의실 배정 (python)

문제 링크 : https://www.acmicpc.net/problem/1931

💡 해결 방법

• 처음엔 시작 시간으로만 정렬해서 정렬 순서로 for문을 돌렸다.
• for문에서 이전 인덱스 끝나는 시간과 다음 인덱스 시작 시간이 조건에 맞으면 count를 증가하면서 마지막까지 끝마치는 식으로 하였다.
• 위의 방식은 시간초과가 났다,, 시작 시간만 정렬할 뿐 아니라 그 다음에 종료시간으로도 오른차순 정렬을 해서 한 번에 회의실 사용하는 시간이 짧아지게 한 번 더 정렬을 한다.

(정답코드 참조)

🖥️ 코드

import sys

N = int(sys.stdin.readline())
arr = [[0, 0] for i in range(N)]
for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    arr[i][0] = a
    arr[i][1] = b
arr = sorted(arr, key=lambda a: a[0])
arr = sorted(arr, key=lambda a: a[1])
count = 1
idx = arr[0][1]

for i in range(1, N, 1):
    if idx <= arr[i][0]:
        idx = arr[i][1]
        count += 1

print(count)

✏️ 알고리즘 분류

• 그리디 알고리즘
• 정렬