회의실 배정
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
풀이
이 문제는 대표적인 그리디알고리즘 문제입니다. 회의를 겹치지 않게 가장 많이 회의를 수행하기 위해서는 회의의 종료시간이 빨라야합니다. 그래야 그 다음 회의를 빠르게 진행할 수 있기 때문입니다. 만약 종료시간이 같은 경우에는 시작시간이 더 빠른 회의부터 나열해야 하겠죠. 그래야 회의시간이 겹쳐지는 회의들을 걸러낼 수 있습니다.
예를 들어서, 4에 끝나는 회의가 2개인데 하나가 1에서 시작하고 나머지가 3에서 시작한 경우에는 이전 회의가 언제 끝나냐에 따라서 둘 중 아무거나 할 수도 있고 하나만 될수도 있으니까요.
이제 코드를 보면서 설명하겠습니다.
import sys
input = sys.stdin.readline
arr = []
# 회의갯수
n = int(input())
# 회의 정보 입력
for _ in range(n):
arr.append(list(map(int, input().split())))
# 회의시간 스케줄 정렬
arr = sorted(arr, key= lambda x : (x[1], x[0]))
# 결과 변수
result = 0
# 현재시간
time = 0
for a in arr:
start = a[0] # 시작시간
end = a[1] # 종료시간
# 현재시간이 시작시간보다 작다면 (회의를 진행할 수 있다면)
# 회의를 진행하고, 종료시간을 시간을 현재시간에 대입
if time <= start:
result += 1
time = end
# 결과 출력
print(result)입력받는 회의 정보는 한줄에 하나씩 입력받으니까, 입력을 다 받고 나서 sorted 메소드를 이용해서 정렬을 수행합니다. 여기서 정렬 기준은 종료시간이고, 같은 종료시간은 빠른시간순으로 정렬시킵니다. 이제 반복문을 이용해서 회의 정보들을 순회하면서 진행할 수 있는 회의의 수를 카운팅하고 결과를 출력하면 됩니다.
