문제
https://www.acmicpc.net/problem/1931
풀이
- 회의가 겹치지 않게 하면서 최대 회의 수
그리디 알고리즘을 사용하는 문제
처음 문제에 접근할 때 빨리 시작하는 순, 회의가 짧은 순으로 접근하려고 했습니다.
# 예제
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
# 최적해
(1,4), (5,7), (8,11), (12,14)빨리 시작하는 순으로 하게 된다면, (0,6), (6,10), (12,14)로 최대 회의 수에 적합하지 않게 됩니다.
회의가 짧은 순으로 접근하게 되면, 효율적이게 동작하지 않을 가능성이 높습니다.
왜냐하면 회의가 짧다고 해서 회의가 더 많은 개수를 만들 수 있다는 보장이 없기 때문이죠.
예를 들어, 짧은 회의가 너무 일찍 끝난다고 해도, 그 회의의 끝나는 시간이 다른 긴 회의의 시작 시간과 겹쳐서 그 긴 회의를 선택할 수 없을 수도 있습니다.
그래서 회의가 빨리 끝나는 순을 기준으로 문제를 풀었습니다.
가장 빨리 끝나는 회의를 먼저 선택하면, 그 이후에 더 많은 회의를 배치할 수 있습니다.
회의를 가장 빨리 끝나는 순으로 정렬해줍니다.
arr = []
n = int(input())
for _ in range(n):
start,end = map(int,input().split()) # 시작 시간, 끝나는 시간
arr.append([start,end])
arr.sort(key=lambda x:(x[1],x[0]))다음으로 끝나는 시간에 가장 인접한 시간대의 다른 시작 시간을 기준으로 카운트합니다.
cnt = 1 # 처음 회의 포함
end = arr[0][1] # 처음 회의 끝나는 시간으로 초기화
for i in range(1,n):
if arr[i][0] >= end: # 다음 회의 시작 시간이 처음 회의 끝나는 시간보다 클 때
end = arr[i][1] # 다음 회의 끝나는 시간으로 업데이트
cnt += 1 # 카운트 증가코드
import sys
input = sys.stdin.readline
arr = []
n = int(input())
for _ in range(n):
start,end = map(int,input().split())
arr.append([start,end])
arr.sort(key=lambda x:(x[1],x[0]))
cnt = 1
end = arr[0][1]
for i in range(1,n):
if arr[i][0] >= end:
end = arr[i][1]
cnt += 1
print(cnt)