백준 실버1 1931. 회의실 배정 (python)

회의실

풀이

문제를 보고 어떻게 할까 구상하다가 처음에는 사용하고 있는 모든 시간을 기록하는 리스트 변수를 생성할까 하다가 굳이 그럴 필요는 없다고 생각되었다.

이유는 현재 회의의 종료 시간이 다음 회의의 시작 시간보다 늦으면 다음 회의는 할 수 없고, 현재 회의의 종료 시간이 다음 회의의 시작시간보다 일찍이면 다음 회의를 시작할 수 있기 때문이다.
이를 이용하는 것을 재귀함수를 이용해서 진행하기 위해 아래처럼 진행을 해봤다.
하지만 시간 초과가 발생했다.

# 한 개의 회의실. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 갯수.
import sys

def check_maxuse(nums, use_time, i):
    global max_use
    if max_use < nums:
            max_use = nums

    if i == N-1:
        return
    else:
        # 현재 종료 시간과 다음 시작 시간 비교
        for j in range(i+1, N):
            if use_time[i][1] < use_time[j][0]:
                check_maxuse(nums+1, use_time, j)
    return


N = int(sys.stdin.readline().strip())
use_time = []
# # 시작 시간과 끝나는 시간은 2**31 -1 보다 작거나 같은 자연수 또는 0.
# using = [0]*(2**31)
# 아니면, (이전 시작, 이전 종료) (지금 시작, 지금 종료)가 있으면
# 이전 종료 < 지금 시작 일 때만 가능한 것으로 확인? 우선 정렬 먼저. 함수 사용해야지.

for _ in range(N):
    use_time.append(list(map(int, sys.stdin.readline().split())))

use_time.sort()
max_use = 0
# 시작하는 시간에 예약한 회의부터 체크하면서 끝까지 다 확인
for i in range(N):
    check_maxuse(1, use_time, i)

print(max_use)

시간 초과 문제를 해결하기 위해 보다 보니 아.. 멍청하게 풀고 있었다. 뭐가 되었든, 일찍 마치는 회의들을 꽉꽉 채워 넣으면 최대한 많은 회의를 진행할 수 있는 것이다.

그래서 다음처럼 풀었다.

1.정렬을 시작 시간이 아닌 종료 시간을 기준으로 정렬
2. 그 중 일찍 시작하는 시간을 집어넣는다.(사실 종료 시간이 같은 애들끼리 있기에 중요치 않다고 본인은 생각)
3. 이제 종료 시간을 기준으로 오름차순 정렬된 회의들을 제일 먼저 종료되는 회의부터 순회하면서, 다음 회의가 진행될 수 있는지 확인하고 되면 추가
4. 종료되면 최대 회의 수를 출력

import sys

N = int(sys.stdin.readline().strip())
use_time = []
for _ in range(N):
    use_time.append(list(map(int, sys.stdin.readline().split())))

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

max_use = 0
end_time = 0

# 회의 예약을 종료되는 순서대로 확인
for i in range(N):
    # 이전 회의가 끝난 후 시작하는 회의만 선택
    if end_time <= use_time[i][0]:
        end_time = use_time[i][1]
        max_use += 1
print(max_use)

근데 질문하기에서 내용을 보니까, 현재 종료시간이랑 다음 시작시간이랑 같아도 되는 것을 확인했다. 테스트케이스는 없어서 확인 못했지만 종료시간과 시작시간이 같아도 +1이 가능함을 알고 있어야 한다.