백준 1931번 회의실 배정

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

1931번: 회의실 배정

 

문제의 핵심: 회의를 많이 진행하려면 명시적 조건을 뭐로 내걸까? 

명시적 조건이란 눈에 '확연히' 보이는, 단순한 조건을 말한다.

생각보다 명시적 조건이 많지 않다.

 

처음에 생각했던 방법: Brute Force로 모든 경우를 배치해볼까?

-> 배치해도 그게 답으로 먀기는 방법은 따른 문제다.

 

방법1. 회의시간이 가장 짧은 것들을 우선배치할까?

-> 순서를 알 수 없기에 기각

방법2. 회의시간이 빠른 것들을 정렬해볼까?

-> (1,1000) (2,3) 처럼 회의시간은 빠른데 늦게 끝나면 말짱 도로목

방법3. 회의시간이 빨리 끝나는 것들을 정렬해볼까?

-> (2,3) (1,4) (3,5) (1,6) (2,7) (3,8) 대충 테스트 케이스를 써봤다. 이거네. 회의시간이 빨리 끝난다는 것은 상대적으로 회의시간이 빨리 시작한다는 뜻이니까. 근데 아닌 경우를 (1,6)부터 써봤는데, 이 경우는 애초에 답에 들어가지도 않아서 무시하면 되겠다. 

 

 

방법3대로 하고, 이젠 순차적으로 진행하되 답만 pick하는 코드를 써보자.

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

ans=end=0

for s,e in time:
    if end <= s:
        ans+=1
        end=e
print(ans)

 

lambda 익명함수 지칭, function처럼 선언 후 사용하지 않고 바로 정의하여 사용

https://velog.io/@oaoong/Python-lambda-%ED%91%9C%ED%98%84%EC%8B%9D

[Python] lambda 표현식