백준 1931 파이썬

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

1931번: 회의실 배정

 

 

if __name__ == '__main__':
    N = int(input())
    work_times = []
    for _ in range(N):
        S, E = map(int, input().split())
        work_times.append((S, E))
    work_times.sort(key=lambda x: (x[1], x[0]))
    ans = 1
    prev_e = work_times[0][1]

    for i in range(1, N):
        work_time = work_times[i]
        start_time = work_time[0]
        end_time = work_time[1]

        if start_time >= prev_e:
            ans += 1
            prev_e = end_time

    print(ans)

# 3
# 1 3
# 8 8
# 4 8

 

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾기 위해 탐욕적 방법을 사용해야한다.

 

 

1. 회의가 빨리 끝나는 순서로 정렬한다. 가장 빨리 끝나는 순으로 정렬해야 가장 많은 회의를 배정할 수 있다.

 

2. 첫번째 원소는 가장 빨리 끝나는 회의이므로 무조건 배정한 후, 끝나는 시간을 기록한다.

 

3. 두번째 원소부터 기록해놓은 이전 회의의 끝나는 시간과 현재 원소의 시작시간을 비교하여 겹치는 시간이 아니면 배정한다.

 

이렇게만 하면 다 풀릴 줄 알았는데  88%에서 오답처리가 됐다.

 

그렇다. 이 문제에는 약간의 함정이 있다.

 

이렇게만 한 경우 아래와 같은 경우 틀린 답이 나온다.

 

# 3
# 1 3
# 8 8
# 4 8

 

이 경우, 최대한 많이 배정할 수 있는 회의는 3 건이다. 

(1, 3) (4, 8) (8, 8)

 

하지만 끝나는 시간만으로 정렬하면 2건을 출력하므로 오답이 된다.

 

끝나는 시간이 같은 경우, 시작 시간이 빠른 순서로 다시 정렬해야만 정답을 얻을 수 있다.

 

즉, 위 1번은 아래와 같이 수정돼야한다.

 

1. 회의가 빨리 끝나는 순서로 1차 정렬, 회의가 빨리 시작하는 순서로 2차 정렬한다.