백준 1931번 : 회의실 배정 (Python)

문제 : www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

풀이

처음에는 시작점을 생각하며 어떻게 껴 넣어야 할지 헤멨다.

메인 아이디어는 끝나는 시점이 빨라야 다음 회의가 들어올 수 있으므로 많은 회의가 가능한 것이다.

따라서 종료 시점을 기준으로 코드를 구성해야 한다.

 

meet 리스트에 입력을 받을때 '종료 시간의 인덱스'에 '시작 시간을 원소'로 넣었다.

(meet[종료시간].append(시작시간))

리스트의 길이는 시간을 입력받을때마다 추가해주었다.

 

meet를 하나씩 돌며 시작 시간이 있는지(입력받은 회의가 있는지) 확인한다.

있다면 (len != 0 이라면) 이전에 종료된 회의 시간(finish)과 시작하는 회의 시간들(meet[i])을 비교하여 회의 시작이 가능한다면 결과값+1을 해준다.

결과값을 하나 더한 뒤에는 루프문을 종료한다.

이때 반례를 생각해주어야 하는데 시작 시간과 종료 시간이 같은 경우다. 이 경우에는 회의가 무한정 가능할 수 있으므로 결과값을 하나 더하더라도 루프를 종료해서는 안된다. 따라서 이 경우를 먼저 모두 처리한 뒤에 해당 원소(시작 시간)를 삭제한다. 그러면 그 다음에 시작 종료 시간이 다른 경우 중 가능한 경우만을 더 추가할 수 있다.

(반례. 1-5, 5-5 OR 5-5, 5-5, 5-5)

 

주석 A와 B의 경우 중 하나만 존재할 수도 있기 때문에 이전 종료 시간(finish) 변경은 조건문마다 달아주었다. 대신 둘다 존재할 경우를 위해 루프 안에서는 미리 저장해 둔 값(finished)을 사용하여 변경에 영향을 받지 않도록 한다.

 

 

N = int(input())
meet = []
finish = 0
result = 0

for i in range(N):
    a, b = map(int, input().split())
    if len(meet)<=b:
        for _ in range(b-len(meet)+1):
            meet.append([])
    meet[b].append(a)

for i in range(len(meet)):
    if len(meet[i]) != 0:
        finished = finish
        while i in meet[i]:           #A 시작=종료
            result += 1
            meet[i].remove(i)
            finish = i
        for start in meet[i]:
            if start >= finished:     #B 시작!=종료
                result += 1
                finish = i
                break
        
            

print(result)