[Python] 1931 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

문제 풀이

A. 접근

회의에서 생각해볼 것은

1. 시작시간 기준으로 가장 빠른 회의
2. 종료시간 기준으로 가장 빠른 회의
   이렇게 고려해볼 수 있다.

그런데 1번의 경우 시작 시간이 빨라도 종료 시간이 늦게 된다면 많은 회의를 할 수 없다. 1시에 시작해서 11시에 끝난다면 회의를 많이 배정할 수 있을까? 학생들도 힘들어서 지칠 것이다.ㅠㅠ

그렇다면 종료시간이 더 중요한 것으로 보인다.

시작 1 3 0 5 3 5 6 8 8 2 12
종료 4 5 6 7 8 9 10 11 12 13 14

이번에는 종료 시간으로 정렬을 해보았는데, 회의가 종료가 되어야지 비로소 다시 회의를 시작할 수 있다.

이런 경우에 어떻게 회의를 구성해야 하냐면,

시작 1 3 0 5 3 5 6 8 8 2 12
종료 4 5 6 7 8 9 10 11 12 13 14

이렇게 총 네 번의 회의를 진행할 수 있다.

즉, 종료시간을 기준으로 정렬하여 매번 종료 시간을 임시로 저장할 변수를 사용하여서, 종료시간보다 시작시간이 더 큰 경우로 회의를 배정한다.

B. 문제 풀이

전체 코드

import sys
input = sys.stdin.readline

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

meeting.sort(key=lambda dt: (dt[1], dt[0]))

cnt = 0
temp = 0

for i in range(N):
    if meeting[i][0] >= temp:
        temp = meeting[i][1]
        cnt += 1

print(cnt)

B-1. 준비

import sys
input = sys.stdin.readline

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

meeting.sort(key=lambda dt: (dt[1], dt[0]))

입력을 모두 받은 후에 정렬을 해준다.
이때, 정렬의 기준을 sort() 함수의 속성값을 통해서 지정할 수 있다.

key 속성에 lambda를 통해서 dt의 1번 인덱스를 먼저, 그리고 0번 인덱스를 나중에 기준으로 정렬한다.

B-2. 풀이

cnt = 0
temp = 0

for i in range(N):
    if meeting[i][0] >= temp:
        temp = meeting[i][1]
        cnt += 1

print(cnt)

카운트를 받을 변수와 종료시간을 받을 변수를 저장한다.

그 이후 모든 스케쥴을 돌면서 종료시간을 기준으로 종료시간보다 시작 시간이 더 느린 경우를 받아서 cnt를 늘린다.

총평

어떻게 풀어야 할지 감을 잡기가 어렵지만, 감을 적당히 잡으면 쉽게 풀이할 수 있는 문제였다.

그래도 어려워 ㅠㅠㅠㅠ 강의 그만해