[알고리즘] 그리디(Greedy) 백준 1931번 - 회의실 배정

N = int(input())

meeting = []
for i in range(N):
    x, y = map(int, input().split(' '))
    meeting.append([x, y])
meeting.sort(key=lambda x: (x[0], x[1]))

target = meeting[0]
result = []
result.append(target)

for i in range(1, N):
    if meeting[i][0] >= target[1]:
        target = meeting[i]
        result.append(target)
    if meeting[i][1] <= target[1]:
        result.pop()
        target = meeting[i]
        result.append(target)
print(len(result))

풀이과정

1. 입력받은 회의실 시간을 정렬한다. [시작 시간, 끝나는 시간] 형태로 meeting 배열에 넣는다.

2. result 배열에 조건에 맞는 회의실을 넣을 것이다. 조건 1)의 경우, 다음 회의실 조건에 부합하기 때문에 result에 append한다. 조건 2)의 경우, 더 많은 회의실을 담을 수 있는 경우 임으로 result에서 기존 회의실을 pop한 후, 새 회의실을 append한다.

    1) target[끝나는 시간] <= meeting[시작시간]
    2) target[끝나는 시간] >= meeting[끝나는 시간]

TIP

sys.stdin.readline

라인이 길어지는 코드의 경우, 입력 받을 때 input() 대신 sys.stdin.readline를 사용하는 것이 좋다. 해당 문제의 경우, 무려 10배나 시간이 차이난다.

import sys
input sys.stdin.readline

N = int(input())

...