[BOJ] 1931번 회의실 배정 문제 - Python

www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

이것도 그렇게 간단한데 왜이렇게 오래걸렸는지 모르겠다.

 

논리의 이해를 위해서 상식적으로 다가가자.

 

회의들이 되게 많으면 제일 빨리 끝나는 것들을 우선적으로 진행시키면 제일 많이 회의할 수 있을 것 아닌가?

 

여기서 포인트는 그러면 같이 끝나는 회의는 누구를 우선으로 할 것인가이다.

 

이것도 상식적으로 다가가면, 어짜피 같이 끝날 것이면 먼저 시작할 회의가 먼저하면 된다.

 

따라서 종료 시간을 기준으로 정렬을 하되, 같은 경우에는 시작 시간으로 정렬이 되면 된다.

 

그럼 이건 의미가 없는 것 아닌가라고 생각할 수도 있는데 문제 조건에 함정이 있다.

 

회의의 시작시간과 끝나는 시간이 같을 수도 있다.

 

저게 왜 문제냐? 다음 예시를 보자.

 

2

2 2

1 2

 

종료시간에 대해서만 정렬을 하면 [2, 2], [1, 2] 일 것이고 앞에서 부터 고려하면 [2, 2]에 대한 회의 1번만 진행한다.

 

하지만 시작 시간을 기준으로 한번 더 정렬을 해서 [1, 2], [2, 2]를 만든다면 2번의 회의가 진행될 것이다.

 

따라서 두 번의 정렬만 해서 종료시간을 기준으로 다음 회의를 찾아가기만 하면 된다.

 

from sys import stdin
input = stdin.readline

N = int(input())
times = []
for _ in range(N):
    times.append(list(map(int, input().rstrip().split())))

times.sort(key=lambda x:(x[1], x[0]))

answer = 0
end = 0
for time in times:
    if time[0] >= end:
        end = time[1]
        answer += 1

print(answer)