[baekjoon] 1931번 : 회의실 배정 (by python)

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

1931번: 회의실 배정

 

정답 code

import sys
input = sys.stdin.readline

n = int(input())

time = [[0]*2 for _ in range(n)]
for i in range(n):
    x, y = map(int,input().split())
    time[i][0] = x
    time[i][1] = y

time.sort(key= lambda x: x[0]) #시작시간순으로 정렬
time.sort(key= lambda x : x[1]) # 끝나는 시간순으로 정렬

cnt = 0
endTime = 0

for i , j in time:
    if i>= endTime:
        cnt += 1
        endTime = j

print(cnt)

 

solution

이번문제의 핵심은 회의를 최대한 많이 진행하기위해 빨리 끝내는 회의부터 정렬해야한다.

 

하지만 같은시간에 끝나는 경우가 있는데 문제에서 시작시간과 끝나는 시간이 같은 경우도 포함하는걸 유의해야한다.

 

만약 이걸 신경쓰지 않는다면 3~4시 회의와 4~4회의가 있는데 신경쓰지 않는경우에는 1번의 회의만 진행 가능하다.

하지만 문제에서는 두개다 가능한 회의임으로 먼저 시작하는걸 앞에 배치해야한다.

 

따라서 회의시간을 시작시간순으로 정렬한후에 끝나는 시간 순으로 정렬하면된다.

 

**정렬시 sort의 key를 이용하여 lambda를 이용

 

그 다음엔 순차적으로 탐색해나가며 회의 시작시간이 전회의 끝나는 시간과 같거나 뒤라면 count하며 진행하면 된다.