1931 회의실 배정 _python

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

1931번: 회의실 배정

회의를 하루종일...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

그리디 알고리즘. 뒤는 생각하지 않고 현재에서 최대한의 욕심을 내라!

시간 간격이 가장 작은것을 넣으려고 하니, 1 4과 3 5같이 입력되면 다른 값과 비교해서 무슨 시간대를 사용할지 모르겠어서 전부 확인해야 하는줄 알았다.

그래서 머리속으로 트리형태로 그려서 생각해보니 재귀형태로 쉽게 풀릴것 같았다.

하지만 범위가 100000까지라서 재귀는 무조건 시간초과가 뜰 것같아서 DP로 생각을 했다.

하지만 DP를 사용하기엔 번거롭기도 해서, 좀 더 고민해보니 방법이 떠올랐다.

 

시간 간격이 짧은 것을 고른다고 생각하는 것에서, 현재 시간에서 최대한 빨리 끝나는 것을 고르는 방법을 떠올렸다.

같은 말이지만 다른느낌.

예제에서 입력이 만약 이렇게 주어진다면?

11
2 13
3 5
0 6
8 12
1 4
5 7
12 14
3 8
5 9
6 10
8 11

 

똑같은 입력이지만 순서만 바꿨더니 한눈에 보이지 않게 된다.

정렬을 해서 (1,4), (5,7), (8,11), (12,14)를 찾기 쉽게 바꿔야한다.

그러기 위해선 정렬을 해줬다.

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

 

정렬을 마치면 원래 예제처럼 나온다.

우선 현재 시간을 0으로 저장해두고 천천히 비교를 해나간다.

어떤 방식으로 비교하냐면, 시작시간이 가장 일찍이면서 현재시간보단 큰 값을 찾는다.

만약 찾으면 끝나는 시간을 현재시간에 저장하면 끝이다.

이러면 현재 시간에서 끝나는 시간이 가장 가까운 시간을 저장하기 떄문에 가장 최적의 시간을 선택하게 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""

"""

N = int(input())
meeting = []
for _ in range(N):
    meeting.append(list(map(int,input().split())))
meeting.sort(key=lambda x : (x[1], x[0]))

ans = 0
curTime = 0
for i in range(N):
    if curTime <= meeting[i][0]:
        curTime = meeting[i][1]
        ans += 1

print(ans)