python 백준 1931 회의실 배정

백준 1931 회의실 배정

 

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

1931번: 회의실 배정

 

문제 : 가장 많이 회의실을 쓸 수 있도록 배치

접근법

 - 그리디 알고리즘 문제였다

 - 그리디 알고리즘은 subprob에서 최적의 해가 전체 prob에서 최적의 해가 되는 것을 증명하는 문제이다

 - 그래서 저는 시작 시간, 끝나느 시간, 시간의 차이로 매트릭스에 저장 후

 - 우선 정렬을 끝나는 시간으로 순서대로 정렬 하였다. 힌트가 큰 도움이 됬다. -> 다음 정렬은 스타트 시간을 순서대로 정렬한다.

 - 그리디 알고리즘은 subprob에서 최적의 해가 전체 prob에 최적의 해가 부정되는 순간 문제자체가 성립 될 수 없다.

 - 그리디 알고리즘으로 문제를 냈다는 것은 위에 과정이 성립될 수 밖에 없단거였고 나는 subprob에서 최적의 해만 찾으면 된다.

 

import sys
sys.stdin = open('inputs.text')

matrix = []
n = int(sys.stdin.readline())
for _ in range(n):
    a,b = map(int,sys.stdin.readline().split())
    dif = b - a
    matrix.append([a,b,dif])

matrix.sort(key=lambda x: (x[1],x[0]))
start,end,diff = matrix.pop(0)
result = []
result.append([start,end,diff])
while matrix:
    start2,end2,diff2 = matrix.pop(0)
    if start2>=end:
        result.append([start2,end2,diff2])
        start=start2
        end=end2
        diff=diff2

print(len(result))