백준 1931 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

n = int(input())
data = []

for i in range(n):
    start_time, end_time = map(int,input().split())
    data.append([start_time,end_time])

data.sort(key=lambda x: (x[1], x[0]))

last = 0
conut = 0

for i, j in data:
  if i >= last:
    conut += 1
    last = j

print(conut)

회의 시간이 겹치지 않으면서 가능한 회의를 가장 많이 할 수 있게 하려면 어떻게 해야하는가?

빨리 끝나는 회의 순서대로 정렬을 해야한다.

빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다.

빨리 시작하는 순서대로 정렬을 우선 한다면, 오히려 늦게 끝날 수 있기 때문이다.
이를 통해 그리디 알고리즘이라는 것과 정렬을 이용해야 한다는 것을 알았다.

 

하나 더 고려할 점은

끝나는 시간이 같다면 빨리 시작하는 순서대로 정렬이 되어야 한다.

예를 들자면

2

2 2

1 2

같은 상황때문에 시작하는 시간의 오름차순으로 정렬을 한번 더 해줘야한다.

그렇기 때문에 정렬을 1. 끝나는 시간의 오름차순 2. 시작하는 시간의 오름차순으로 해주어야 한다.