백준 회의실 배정 파이썬

문제링크

1931번: 회의실 배정

밤을새서 정신이없다

구상단계

단번에 해결책이 떠오르지않았다 계속해서 드는생각은 이걸 그리디알고리즘으로 풀수있나? 라는생각이었다

알고리즘분류에 그리디알고리즘, 정렬이라고 되어있었고

가장 회의시간이 짧은 회의들 우선으로 계속 추가하는건가? 라는 생각이들었다

 

하지만 그것도 곧 그만두게 된것이 반례를 찾았기때문이다

 

시간을 기준으로 동적프로그래밍식으로 접근을 해야하나 싶었지만

끝나는시간의 범위가 0부터 2의 31승인것을보고 맘을 접었다

 

다른방법을 생각해보다가 결국 알고리즘 분류가 정렬이라고 되있었기때문에

정렬을 사용한 해결방법을 계속 생각해보았고 노트에 예제를 그려보다가 아이디어를 찾았다

 

가방안에 최대한 많은 물건을 넣듯이

정해진 시간안에 최대한 많은 회의를 넣는 느낌이라고 생각해보자

 

같은수의 회의를 할때는 더 빨리끝나는게 좋다(그 뒤로 최대한 많은 회의를 넣을수있으니까)

회의는 겹칠수 없다

구현

import sys
input=sys.stdin.readline
N=int(input())
al=[]
for i in range(N):
    a,b=map(int,input().split())
    al.append([a,b])
# 회의 시작시간을 기준으로 정렬
al.sort(key=lambda x: (x[0], x[1]))
# 계산시작
ans=1
end=al[0][1]
for i in range(1,N):
    # 안겹칠경우
    if al[i][0] >= end:
        ans+=1
        end=al[i][1]

    # 겹칠경우
    else:
        if al[i][1] < end:
            end=al[i][1]
print(ans)

정답, 게다가 속도도 빠르다

 

1,1 처럼 시작하자마자 끝나는 회의때문에 조금 골머리가 아팠다

애매한부분에 대해 설명을 하자면

시작하자마자 끝나는 회의도 회의로 침

시작하자마자 끝나는 회의는 여러개 들어가도 상관없음

정도가 있겠다 사실 시작과 끝이 같은 회의를 겹치는 회의로 보지않기때문에 원래 저게 맞는거지만

이때문에 시간을 많이 소비했다 

아마 다른분들도 시작하자마자 끝나는 회의때문에 많이 틀리신것같다