백준 1931번 회의실 배정 파이썬 (python code)

난이도: 실버2
번호: 1931번

 

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

이중배열도 키를 지정해서 sort할 수 있는지 몰라서 직접sorting을 해야하는줄 알고 조금 헤맸는데

sort(key= lambda x:x[n])으로 n번째 index에 대해 sort할 수 있어서 이를 사용했다.

또한 파이썬의 sort함수는 안정성을 만족하므로

table.sort(key=lambda a: a[0])
table.sort(key=lambda a: a[1])

를 이용하면 idx 1을 기준으로 오름차순 정렬하되 같으면 idx 0을 기준으로 오름차순 정렬할 수 있다.

 

이를 이용해서 가장일찍끝나는 회의를찾아 더하는 방식으로 해결했다.

(찾은 회의가 끝나면 끝난시간 이후 시작하는 회의중 일찍 끝나는 회의를 찾는 방식을 반복)

 

import sys

meetings = int(sys.stdin.readline().rstrip())
table=[0]*meetings
for i in range(meetings):
    table[i] = list(map(int,sys.stdin.readline().split()))
table.sort(key=lambda a: a[0])
table.sort(key=lambda a: a[1])
num_meetings=0
end=0
for idx in range(meetings):
    if table[idx][0]>=end:
        num_meetings+=1
        end=table[idx][1]
print(num_meetings)