1931번: 회의실 배정

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

---

 

그리디 문제다.

 

그리디 문제는 주로 정렬과 관련되어 있다.

이 문제도 N이 최대 10만이고, 시간 제한은 2초이므로 O(NlogN)까지 가능하다.

 

회의를 최대한 많이 넣어야 한다.

그러므로, 회의의 종료시간을 기준으로 오름차순 정렬한다.

 

그리고 여기서 주의할 점은, 두번째 정렬 기준으로 회의의 시작시간 기준으로 오름차순 정렬해야한다는 것이다.

왜냐하면 이런 경우 때문이다.

 

예를 들어

6 10

13 13

12 13

11 13

이렇게 회의 시간이 있다고 해보자.

만약, 회의의 종료시간만을 기준으로 오름차순 정렬했다면, 

반복문을 돌며 들어가는 회의는

(6, 10) - (13, 13)이 될 것이다.

하지만, 이렇게 회의를 넣으면, 회의의 최대개수가 나오지 않는다.

(6, 10) - (11, 13) - (13, 13)이 최대 개수인 경우이기 때문이다.

그러므로 두번째 정렬기준으로 회의의 시작시간 기준으로 올므차순 정렬도 해줘야 한다.

 

정렬 후, 반복문을 돌면서 이전 회의의 종료 시간보다 현재 확인하는 회의의 시작시간이 더 클 경우에는 해당 회의를 집어넣는다.

그리고, 회의 종료시간을 집어 넣은 회의의 종료 시간으로 갱신해준다.

 

위 과정을 반복하면서 반복문을 1번만 돌면, 회의의 최대 개수를 확인할 수 있다.

 

---

# 1931번: 회의실 배정

n = int(input())
arr = [] # 회의 시간을 저장하는 리스트
for _ in range(n):
    time = list(map(int, input().split()))
    arr.append(time)


# 회의 끝 시간 기준으로 오름차순 정렬 / 회의 시작시간 기준으로 오름차순 정렬
arr.sort(key = lambda x:(x[1], x[0])) 


cnt = 1 # 일단 처음 회의는 넣고 시작하므로
end_time = arr[0][1] # 맨 처음 회의의 끝 시간 초기화

for i in range(1, n):
    if arr[i][0] >= end_time: # 확인하는 회의의 시작 시간이 이전 회의의 끝 시간보다 큰 경우
        cnt += 1 # 회의 추가
        end_time = arr[i][1] # 끝 시간은 추가된 회의의 끝 시간으로 변경


print(cnt)

 

그리디 문제는 그냥 풀이가 팍 떠오를 때는 바로 풀리는데,

안 떠오를 때는 아예 안풀리는 것 같다..

많이 풀어보는 수 밖에