[백준] 1931. 회의실 배정

문제

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

1931번: 회의실 배정

 

설계

- 첫번째 조건 : 회의가 빨리 끝날수록 뒤에 회의를 많이 잡을 수 있기 때문에 회의가 빨리 끝나는 시간을 최우선으로 정렬한다.

- 두번째 조건 : 회의 시간이 (1, 3), (3, 3)일 경우 먼저 1시에 회의를 먼저 하고 끝내야 3시 회의를 하여 회의를 2번 할 수 있다. 때문에 회의 종료시간이 같을 경우 빨리 시작하는 기준으로 정렬한다.

- 위 두가지 조건을 모두 종합했을 때 시작시간 기준 정렬 → 종료시간 기준 정렬을 해야만 우리가 원하는 위 두가지 조건을 만족시킬 수 있다.

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

arr.sort()  # 먼저 시작하는 순서대로 정렬
arr.sort(key=lambda x: x[1])    # 먼저 끝나는 순서대로 정렬

cnt = 1		# 처음 회의 종료 후부터 확인
end = arr[0][1]     # 처음 회의가 끝나는 시간 setting
for i in range(1, N):
    if arr[i][0] >= end:    # 다음 회의 시작이 앞전 회의가 끝난 후 시작한다면
        cnt += 1			# 회의 가능 개수를 더해준다
        end = arr[i][1]     # 회의가 끝나는 시간 갱신

print(cnt)