문제
n개의 회의
각 회의는 시작시간, 끝나는 시간 주어짐. 기준 2개
회의가 겹치지 않게 하면서 회의실 사용할 수 있는 회의의 최대 개수
끝나는 시간 기준 정렬.
n <= 100,000 N^2 안된다.
내 코드
import sys
sys.stdin = open("input.txt", "rt")
# n개의 회의
# 각 회의는 시작시간, 끝나는 시간 주어짐. 기준 2개
# 회의가 겹치지 않게 하면서 회의실 사용할 수 있는 회의의 최대 개수
# 끝나는 시간 기준 정렬.
# n <= 100,000 N^2 안된다.
n = int(input())
data = []
for _ in range(n):
start,end = map(int, input().split())
data.append((start,end))
data.sort(key = lambda x : (x[1], x[0])) # 끝나는 시간 기준 정렬, 같으면 시작시간
end = data[0][1] # 가장 마지막 회의의 끝나는 시간과 비교해야 함.
cnt = 1
for i in range(1,n):
if data[i][0] >= end:
cnt += 1
end = data[i][1]
print(cnt)코멘트
해당 문제는 그리디적으로 풀었어야 했따.
위 문제는 최대한 많이 배정하거나 선택하는 문제. 즉 활동 선택 문제에 해당한다.
간단하게 설명하면, 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제이다. 위에서는 각 회의가 겹치지 않게 최대한 많은 회의를 배정하는 것으로 나와있다.
이러한 문제들의 특징은 한 사람이 하나의 활동에 대해서만 작업할 수 있다는 점.
즉, 하나의 활동을 완료하기 전까지는 다른 활동을 선택할 수 없다는 것. 하나의 활동을 선택하면 나머지 겹치지 않는 활동에 대해서 독립적이고, 탐욕 선택이 이후의 결과에 영향을 미치지 않는다.
그리디 알고리즘 적용
이전 선택의 결과가 이후의 결과에 영향을 미치지 않으려면 먼저 이전 선택의 종료 시간과 이후 선택의 시작 시작이 서로 겹치지 않으면 된다. 그리고 최대한 많은 활동을 선택하려면 종료시간이 빨라야 할 수 밖에 없을 것.
-> 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것.
다만 주의해야 할 점이 종료시점을 기준으로 오름차순으로 정렬해주되, 종료시점이 같을 경우 시작시점을 오름차순으로 정렬해주어야 한다.
ex)
8 8
4 8
1 3
위와 같은 입력이 있을 때 종료 시점으로만 정렬하면
1 3
8 8
4 8
다음과 같이 정렬될 수 있다.
문제는 위와 같이 정렬되면 1,3이 선택되고 마지막 회의의 끝나느 시간을 3으로 갱신한다.
그 다음 8,8이 선택되면 마지막 회의 종료시간이 8이 된다. 그렇게 되면 4,8을 선택할 수 없게 된다.
