[ BOJ 1931 ] 회의실 배정(Python)

문제

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

회의실은 단 한 개, 회의 시간이 겹치지 않게 최대한 많은 회의를 해보자.

문제 풀이

틀린 풀이

• 시간 초과 발생 🤓
  당연함. for문 - while문으로 O(n^2) 임
• 야무지게 sorted로 잘 정렬하고, 왜 그랬는지 의문

import sys
input = sys.stdin.readline

n = int(input())
times = sorted([list(map(int,input().rsplit())) for _ in range(n)])

answer = 0
for i in range(n):
    index, temp = i, [(times[i])]
    j = i + 1
    while j < n:
        start, end = times[index]
        n_start, n_end = times[j]

        if end > n_start:
            j += 1
        else:
            temp.append((n_start, n_end))
            index = j
            j = index + 1
    
    answer = max(answer, len(temp))

print(answer)

올바른 풀이

• 배열을 정렬했다면 for문 한 개로도 풀이가 가능하다!

times = sorted([list(map(int,input().rsplit())) for _ in range(n)], key=lambda x: (x[1],x[0]))

회의가 끝나는 시간이 빠른 순으로 정렬해주었다.
➕ 끝나는 시간이 같은 경우엔 시작 시간이 빠른 순으로 정렬

start, end = times[0]
cnt = 1
for i in range(1, n):
    n_start, n_end = times[i]
    if end <= n_start:
        start, end = n_start, n_end
        cnt += 1

1. 끝나는 시간이 가장 빠른 회의를 start, end에 할당
2. 다음 회의 시간을 n_start, n_end에 할당
3. 회의가 끝난 뒤 다음 회의를 시작할 수 있으면 end <= n_start
   회의 시작 start, end = n_start, n_end
4. 모든 회의 시간을 체크해줌

🤓 한 줄 정리
현재 회의가 끝났을 때, 시작할 수 있는 회의가 있다면 카운트 해준다.

코드

import sys
input = sys.stdin.readline

n = int(input())

times = sorted([list(map(int,input().rsplit())) for _ in range(n)], key=lambda x: (x[1],x[0]))

start, end = times[0]
cnt = 1
for i in range(1, n):
    n_start, n_end = times[i]
    if end <= n_start:
        start, end = n_start, n_end
        cnt += 1

print(cnt)