[알고리즘] Java / 백준 / 강의실 배정 / 11000

[알고리즘] Java / 백준 / 강의실 배정 / 11000

문제

문제 링크

접근 방식

1. 강의 시작 시간과 종료 시간을 가지는 Lecture 클래스를 생성한다
2. 강의 시작 시간을 우선순위로 하여 우선순위 큐에 강의 객체를 넣는다
3. 강의 종료 시간을 가지는 우선순위 큐를 생성한다. 이 때 이 강의 종료 시간의 의미는 각 강의실의 종료 시간이므로 해당 큐의 크기는 강의실의 개수를 의미한다
4. 강의 객체를 가진 우선순위 큐를 하나씩 빼서 각 강의실의 종료 시간과 강의의 시작 시간을 비교하고, 강의의 시작 시간이 강의실의 종료 시간보다 크거나 같으면 (강의실을 쓸 수 있으면) 해당 종료 시간을 없애고 강의의 종료 시간을 넣는다. 반대로 강의의 시작 시간이 강의실의 종료 시간보다 작으면 기존의 강의실은 놔두고 현재 강의의 종료 시간을 넣는다
5. 강의 종료 시간을 가지는 우선순위 큐의 크기를 출력한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_11000 {
	
	public static class Lecture implements Comparable<Lecture>{
		
		int start;
		int end;
		
		Lecture(int start, int end){
			this.start = start;
			this.end = end;
		}
		
		@Override
		public int compareTo(Lecture o) {
			
			return this.start - o.start;
		}
		
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		PriorityQueue<Lecture> pq = new PriorityQueue<>();
		
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			pq.offer(new Lecture(start,end));
		}
		
		
		PriorityQueue<Integer> endPq = new PriorityQueue<>();
		
		while(!pq.isEmpty()) {
			Lecture data = pq.poll();
			if(endPq.isEmpty()) {
				endPq.offer(data.end);
			}
			else {
				// 기존 강의실이 존재하면 강의실의 종료 시간 중 최소 값과 비교
				// 만약 강의실 종료 시간보다 시작 시간이 크거나 같으면 종료 시간 갱신
				if(data.start >= endPq.peek()) {
					endPq.poll();
					endPq.offer(data.end);
				}
				
				// 강의실 종료 시간보다 시작 시간이 작으면 강의실 추가 (강의실 종료 시간 추가)
				else {
					endPq.offer(data.end);
				}
			}
		}
		
		
		System.out.println(endPq.size());
	}

}