문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.
각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
풀이
풀이 전 메모
실제로 내가 직접 회의실을 배정하는 과정을 그려봤을때,
시작 시간이 제일 빠른 것 부터 차례로 보면서 끝나는 시간이 제일 짧은 걸 찾았었다.
그리고 그 끝나는 시간과 가장 가까운, 다음 회의 시작 시간을 찾고, 그 회의가 끝나는 시간이 가장 짧은것을 찾았다.
방법 1.
시작시간 기준 오름차순 정렬하고,
시작시간 + 끝나는 시간 텀이 가장 짧고 안겹치는 애들로만 result에 담기
방법 2.
시작시간 기준, 끝나는 시간 기준 총 두 번 정렬 하고나서
앞선 회의의 끝나는 시간이 다음 회의의 시작시간 보다 크면 count - 1
변수
n : 회의 갯수
meeting : 회의 시간을 담을 리스트
cnt : 최종적으로 수행할 수 있는 회의 갯수, 겹치는 회의는 차감할 예정
end : 첫번쨰로 배정한 회의의 끝나는 시간For-Loop 1. Input
문자열 타입으로 입력을 받은 후, 각 리스트를 순회하면서 int 타입으로 형변환한다.
for i in range(n):
meeting.append(input().split())For-Loop 2. TypeCasting
for item in meeting:
item[0] = int(item[0])
item[1] = int(item[1])Sort - 시작시간
시작시간 정렬
meeting.sort(key=lambda x: x[0])Sort - 끝나는 시간
시작시간 정렬
meeting.sort(key=lambda x: x[1])For-Loop 3. - 카운팅
오름차순 정렬을 했으므로, 맨 첫 인덱스에 있는 회의는 넣고 시작한다.
그 회의의 끝나는 시간이 그 다음 회의의 시작시간보다 크면(늦게끝나면)
그 다음 회의는 진행할 수 없는 것이므로 cnt -1 을 해준다.
그렇지 않으면 카운트는 유지, 회의가 끝나는시각을 담고있는 end 만 갱신해준다.
end = meeting[0][1]
for i in range(1, n):
if meeting[i][0] < end:
cnt -= 1
else:
end = meeting[i][1]배정할 수 있는 회의의 갯수 출력
CODE
import sys
input = sys.stdin.readline
n = int(input())
meeting = list()
cnt = n
# 입력
for i in range(n):
meeting.append(input().split())
# int로 형변환
for item in meeting:
item[0] = int(item[0])
item[1] = int(item[1])
# 시작시간 정렬
meeting.sort(key=lambda x: x[0])
# 종료시간 정렬
meeting.sort(key=lambda x: x[1])
end = meeting[0][1]
for i in range(1, n):
if meeting[i][0] < end:
cnt -= 1
else:
end = meeting[i][1]
print(cnt)