알고리즘 잘 푸는법 : 문제 이해가 우선 (실버2)

#1931번 회의실 배정 https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

회의 시작 시간과 종료 시간이 주어지면, 최대한 많은 회의를 진행하는 경우에 몇 개의 회의를 진행할 수 있는지를 출력하면 된다.

 

처음에 나는 모든 경우의 수를 다 계산하려 했다.

 

근데 시간초과가 났다. 여러 방법을 추가했지만 시간초과였다.

 

정답은 굉장히 단순했다.

 

그냥 정렬하고 순서대로 계산하면 된다.

task = [list(map(int, input().split())) for _ in range(int(input()))]
task = sorted(task, key=lambda a: a[0])
task = sorted(task, key=lambda a: a[1])
last = 0
cnt = 0
for i, j in task:
    if i >= last:
        cnt += 1
        last = j
print(cnt)

 

회의 시작시간을 기준으로 정렬한 뒤

회의 종료시간을 기준으로 한번 더 정렬한다.

 

그 뒤에 계산하면 된다.

 

이렇게 간단하다는 사실에 좀 충격이었다.

 

시작시간으로만 정렬하면, 일찍 시작하고 늦게 끝나는 회의로 인해 시간을 독식당할 수 있다.

종료시간만으로 정렬하면, 에초에 늦게 시작하게된다.

 

시작시간으로 정렬한 뒤 종료시간으로 정렬하게되면 위 두 가지 방법이 지닌 각각의 문제점을 중철시킨

좋은 방법이 된다.

 

사실 아직도 납득이 안된다.

 

 

+) sorted함수는 정렬을 하는데, key인자를 받는다. lambda함수를 통해 리스트 내 인덱스를 전달할 수 있다.