[Java] 백준 1374번 : 강의실

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

예제 입력 1

8
6 15 21
7 20 25
1 3 8
3 2 14
8 6 27
2 7 13
4 12 18
5 6 20

예제 출력 1

5

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N;
	private static int no, start, end;
	private static List<Class> classes;
	
	static class Class implements Comparable<Class> {	// 강의실 정보를 저장할 클래스
		int no, start, end;	// 강의실 번호, 시작 시간, 끝나는 시간

		public Class(int no, int start, int end) {
			super();
			this.no = no;
			this.start = start;
			this.end = end;
		}

		@Override
		public String toString() {
			return "Class [no=" + no + ", start=" + start + ", end=" + end + "]";
		}

		@Override
		public int compareTo(Class o) {	// 시작 시간 기준으로 오름차순 정렬하되, 시작 시간이 같으면 종료 시간 기준으로 오름차순 정렬
			if(this.start==o.start) return Integer.compare(this.end, o.end);
			return Integer.compare(this.start, o.start);
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		classes=new ArrayList<>();
		PriorityQueue<Integer> pq=new PriorityQueue<>();
		
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			no=Integer.parseInt(st.nextToken());
			start=Integer.parseInt(st.nextToken());
			end=Integer.parseInt(st.nextToken());
			classes.add(new Class(no, start, end));
		}
		Collections.sort(classes);
		
		int result=0;
		for(int i=0;i<N;i++) {
			while(!pq.isEmpty() && pq.peek()<=classes.get(i).start) {	// 우선순위 큐에 값이 존재하고, 해당 값이 현재 강의 시작 시간 이하이면 우선순위 큐에서 제거함
				pq.poll();
			}
			pq.add(classes.get(i).end);	// 현재 강의 끝나는 시간을 우선순위 큐에 저장
			result=Math.max(result, pq.size());	// 우선순위 큐에 들어가는 값들 중 최대인 경우를 구함
		}
		
		System.out.println(result);
	}

}

1. 강의 시작 시간 기준으로 오름차순 정렬합니다.

2. 반복문을 돌며 우선순위 큐에 강의 끝나는 시간을 저장하는데, 이때...

3. N개의 강의를 각각 탐색하며 이전 강의 끝나는 시간과 현재 강의 시작 시간을 비교합니다.

    3-1. 이전 강의 끝나는 시간 <= 현재 강의 시작 시간 : 우선순위 큐의 값을 하나 빼냅니다.

    3-2. 이전 강의 끝나는 시간 > 현재 강의 시작 시간 : 우선순위 큐의 값을 그대로 둡니다.

4. 2번을 수행하고 현재 최댓값과 우선순위 큐에 저장된 값의 개수 중 더 큰 값을 최댓값에 저장합니다.

5. 최종적으로 최댓값에 저장된 값을 출력합니다.