[백준] 11000번: 강의실 배정 - JAVA

문제 바로가기> 11000번: 강의실 배정

 

그리디 알고리즘으로, 우선순위 큐를 이용해서 풀 수 있다.

 

1 ≤ N ≤ 200,000이므로 브루트포스를 돌리면 당연히 시간초과가 난다.
따라서 정렬을 이용한 우선순위 큐를 이용해 그리디 알고리즘으로 풀어야 한다. 

 

정렬 기준

그렇다면 어떤 기준으로 정렬을 해야할까?

처음에 필자는 종료시각을 기준으로 (빨리 끝나는 시각 순으로 오름차순) 정렬을 해서 틀렸다...

시작 시각으로 정렬을 해야 앞에서부터 차곡 차곡 강의 간의 텀을 짧게 해 배정이 가능한 것이었다.

 

종료 시간을 우선순위 큐에 넣고 비교

정렬 자체는 시작 시각을 기준으로 하였지만, 결국 어떤 강의가 들어갈 자리를 찾기 위해서는 종료시각과 비교를 해야 한다.

따라서 그러기 위해서는 종료 시각을 담는 우선순위 큐가 필요하다. 이때 당연히 오름차순으로 정렬을 해야 한다.

그렇다면 우선순위 큐에서 top위치값은 종료시각이 가장 빠른 강의의 종료시각이 된다.

그리고 앞에서 정렬한 모든 강의의 시작 시각과 우선순위 큐의 top와 비교한다. (반복문)

 

만약, 현재 강의의 시작 시각 >= 우선순위 큐의 top (종료시각) 

• 우선순위 큐에서 top에 있는 강의를 poll() (제거)
• 현재 강의의 종료시각을 우선순위 큐에 넣는다. 

-> 원래 있던 강의실에 다음 강의를 배정하는 것이다. (우선순위 큐의 사이즈 변하지 않음)

 

아니라면

• poll() x
• 현재 강의의 종료 시각을 우선순위 큐에 넣는다.

-> 새로운 강의실에 강의를 배정하는 것이다. (우선순위 큐의 사이즈 1 증가)

 

그리고 모든 강의가 배정이 되었다면, 우선순위 큐의 사이즈가 강의실의 개수가 된다.

 

---

왜 종료시각을 기준으로 오름차순하면 안될까?

반례를 통해 종료시각을 기준으로 오름차순 정렬을 하면 안되는 이유를 살펴보자.

1 3
2 5
4 12
7 8
7 11
9 10

이렇게 입력이 주어졌다고 하자

 

 

1) 시작시각 오름차순 정렬

오름차순으로 시작 시각을 정렬하면 

1 3 - 강의 1
2 5 - 강의 2
4 12 - 강의 3
7 8 - 강의 4
7 11 - 강의 5
9 10 - 강의 6

이렇게 강의실이 저장이 된다.

 

강의 1부터 강의 6까지 반복해서 강의의 시작시각과 우선순위 큐의 종료시각을 비교하면 된다.

 

강의 1에서는

종료시각이 3이므로, 

우선순위 큐: 3

1	2	3
강의실A	강의1

 

 

강의 2에서는

우선순위 큐의 top(3)>현재 강의실의 시작시각(2)이므로 poll x

우선순위 큐: 3, 5

1	2	3	4	5
강의실A	강의1
강의실B		강의2

 

강의 3에서는

우선순위 큐의 top(3)<현재 강의실의 시작시각(4)이므로 poll o

우선순위 큐: 5, 12

1	2	3	4	5	6	7	8	9	10	11	12
강의실A	강의1			강의3
강의실B		강의2

 

강의 4에서는 

우선순위 큐의 top(5)<현재 강의실의 시작시각(7)이므로 poll o

우선순위 큐: 8, 12

1	2	3	4	5	6	7	8	9	10	11	12
강의실A	강의1			강의3
강의실B		강의2					강의4

 

강의 5에서는 

우선순위 큐의 top(8)>현재 강의실의 시작시각이므로 poll x

우선순위 큐: 8, 11, 12

1	2	3	4	5	6	7	8	9	10	11	12
강의실A	강의1			강의3
강의실B		강의2					강의4
강의실C							강의5

 

강의 6에서는

우선순위 큐의 top(8)<현재 강의실의 시작시각이므로 poll o

우선순위 큐: 10, 11, 12

1	2	3	4	5	6	7	8	9	10	11	12
강의실A	강의1			강의3
강의실B		강의2					강의4		강의6
강의실C							강의5

 

따라서 강의실은 총 3개가 나온다.

 

2) 종료시각 오름차순 정렬

오름차순으로 종료 시각을 정렬하면

1 3 - 강의 1
2 5 - 강의 2
7 8 - 강의 3
9 10 - 강의 4
7 11 - 강의 5
4 12 - 강의 6

이렇게 강의실이 저장이 된다.

 

강의 1부터 강의 6까지 반복해서 강의의 시작시각과 우선순위 큐의 종료시각을 비교하면 된다.

 

강의 1에서는

종료시각이 3이므로, 

우선순위 큐: 3

1	2	3
강의실A	강의1

 

 

강의 2에서는

우선순위 큐의 top(3)>현재 강의실의 시작시각(2)이므로 poll x

우선순위 큐: 3, 5

1	2	3	4	5
강의실A	강의1
강의실B		강의2

 

강의 3에서는

우선순위 큐의 top(3)<현재 강의실의 시작시각(7)이므로 poll o

우선순위 큐 :  5, 8

1	2	3	4	5	6	7	8
강의실A	강의1						강의3
강의실B		강의2

 

강의 4에서는

우선순위 큐의 top(5)<현재 강의실의 시작시각(9)이므로 poll o

우선순위 큐: 8, 10

1	2	3	4	5	6	7	8	9	10
강의실A	강의1						강의3
강의실B		강의2							강의 4

 

강의 5에서는

우선순위 큐의 top(8)>현재 강의실의 시작시각(7)이므로 poll x

우선순위 큐: 8, 10, 11

1	2	3	4	5	6	7	8	9	10	11
강의실A	강의1						강의3
강의실B		강의2							강의 4
강의실C							강의5

 

강의 6에서는

우선순위 큐의 top(8)>현재 강의실의 시작시각(4)이므로 poll x

우선순위 큐: 8, 10, 11, 12

1	2	3	4	5	6	7	8	9	10	11	12
강의실A	강의1						강의3
강의실B		강의2							강의 4
강의실C							강의5
강의실 D				강의6

 

따라서 종료시각을 기준으로 오름차순 정렬하면 총 4개의 강의실이 생기고 시작시각을 기준으로 오름차순 정렬하면 총 3개의 강의실이 생기므로 시작시간을 기준으로 오름차순해야 최소의 강의실 개수가 도출된다.