#160 백준 파이썬 [1931] 회의실배정 - 그리디 알고리즘

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

 

 

#Solution

두 가지 코드를 시도해보았다.

1. 시작시간을 lambda 함수로 오름차순 정렬한 뒤, 가장 뒤 회의 부터 가능한 maximum 회의 수를 출력하는 방법

2. 끝나는 시간 -> 시작 시간 차례로 오른차순 정렬한 뒤, 끝나는 시간이 가장 이른 시간 부터 차곡차곡 더해가는 방법

 

결국 빨리 끝나는 것 중 빨리 시작하는 순서(시작과 끝이 같은 경우의 수를 걸러줌)대로 집어 넣으면,

더 빠르게 답을 구해낼 수 있다.

 

1번은 자체적으로 만든 함수로 O(nlogn)이 걸린다(고 생각했지만 O(n^2)이다). 물론 답은 맞다(반례 있을 수도).

2번은 람다를 두 번 활용하는 함수로 O(nlogn)의 시간복잡도가 걸린다. 결론은 내장함수가 더 효율적이다.

 

 

1. 시간 초과 나는 코드

import sys

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

meeting = sorted(meeting, key = lambda x: [x[1], x[0]])  


#뒤에서 부터 maximum 회의 수를 구해준다
max_meeting = [0 for _ in range(N)]

for i in range(1, N+1):
    for j in range(i):
        if i == 1:
            max_meeting[-i] = 1
        else:
            if meeting[-i][1] <= meeting[-i+j][0]:
                if max_meeting[-i] < max_meeting[-i+j] + 1:
                    max_meeting[-i] = max_meeting[-i+j] + 1
    
    if not max_meeting[-i]:
        max_meeting[-i] = 1


print(max(max_meeting))

 

2. 정답 코드

import sys

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

meeting = sorted(meeting, key = lambda x: [x[1], x[0]])


#빨리 끝나는 것 중 가장 빨리 시작하는 순서대로 더해준다.
max_meeting = 0
start = 0
for meet in meeting:
    if meet[0] >= start:
        start = meet[1]
        max_meeting += 1
        
print(max_meeting)