[백준 1931번] 회의실 배정 (java)

www.acmicpc.net/problem/1931

1931번: 회의실 배정

한 개의 강의실에 최대한 많은 회의를 넣기 위해서는 각 회의마다 끝나는 시간을 기준으로 오름차순 정렬을 해줘야 한다. 왜냐하면 앞에 회의가 일찍 끝날수록 뒤에 더 많은 회의가 회의실을 사용할 수 있기 때문이다.

 

먼저, 회의의 시작 정보와 끝나는 정보를 담은 Class 클래스를 생성하였다.

그리고 끝나는 시간이 짧은 순서대로 우선순위를 두어서 모든 Class를 우선순위 큐에 넣는다.

 

가장 먼저 큐에서 빠져나오는 회의는 모든 회의들 중 가장 일찍 끝나는 회의가 될 것이다.

예를 들어 문제 예제에서 (1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14) 다음과 같을 때, 가장 먼저 우선순위 큐에서 빠져나오는 회의는 (1, 4)이다.

이 회의가 끝나는 시간은 4이다. 그러면 가장 최근에 회의실에서 회의가 끝난 시간은 4이므로

end = 4 로 한다. (end는 현재 시점에서 가장 최근에 끝낸 회의의 종료 시간을 나타내는 변수)

그리고 첫 회의를 끝냈으므로 카운트를 증가시킨다.

 

그 다음, 또 다시 우선순위 큐에서 회의를 꺼내는데, 주의해야할 것은 두번째부터는 꺼내진 회의의 시작 시간이 end보다 크거나 같아야 한다는 점이다.

마지막으로 끝낸 회의의 종료 시간보다 먼저 시작할 수는 없기 때문이다.

만약, end와 동시에 시작하거나 늦게 시작한다면, end를 방금 꺼낸 회의의 종료 시간으로 변경해주고

카운트를 증가한다. 

 

위의 예제에서 (1, 4) 다음에 우선순위 큐에서 꺼내지는 회의는 (3, 5) 이다. 그러나 이 회의는 이 전 회의의 종료시간인 4보다 먼저 시작하므로 회의실을 사용할 수 없다. 

그러므로 다시 우선순위 큐에서 새로운 회의를 꺼내야 한다.

이번에는 (0, 6)이 꺼내지지만 역시 마찬가지로 4보다 시작시간이 앞서므로 회의실을 사용할 수 없다.

그 다음, (5, 7)의 경우에는 시작시간이 4보다 뒤에 있으므로 회의실을 사용할 수 있기 때문에

end = 7로 변경해주고 카운트를 증가한다.

 

이런식으로 계속 큐에서 종료시간이 작은 순서대로 회의를 꺼낸 후 종료시간이 end보다 크거나 같으면 카운트를 증가시켜서 회의실을 사용할 수 있는 총 회의의 수를 구할 수 있다.

 

소스코드 :