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

문제 설명

1. N개의 강의가 주어진다.

2. 강의의 시작시간/끝시간이 주어진다.

3. 강의는 서로 겹치면 안되고, 모든 강의를 성공적으로 할 수 있는 최소 강의실 수를 return하면 된다.

풀이 과정

 1. 우선순위 큐, 그리디와 관련된 문제이다.

 2. 가장 빨리 끝나는 강의의 끝시간보다 그 다음에 가장 빨리 끝나는 과목의 시작 시간이 더 이르면 강의실을 하나씩 늘려주면 된다.

 3. 딱히 설명할 내용이 없다.... 주석으로 적어둠

코드

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int course[][] = new int[N][2];
	// 0 -> 시작시간, 1 -> 끝시간
	for(int i=0; i<N; i++){
	course[i][0] = sc.nextInt();
	course[i][1] = sc.nextInt();
	}
	// 강의를 끝나는 시간에 맞춰 정렬해 준다.
	Arrays.sort(course, new Comparator<int[]>(){
	public int compare(int[] o1, int[] o2){
	if(o1[0] == o2[0]) return (o1[1] - o2[1]);
	else return (o1[0] - o2[0]);
	}
	});
	// 필요한 강의실의 개수를 가질 rooms
	PriorityQueue<Integer> rooms = new PriorityQueue<>();
	// 강의를 시작하고
	for(int i=0; i<N; i++){
	// 사용중인 강의실이 없으면 시작점을 넣어준다.
	if(rooms.isEmpty()){
	rooms.add(course[i][1]);
	continue;
	}
	if(rooms.peek() <= course[i][0]) rooms.remove(); // 지금 강의는 현재 가장 빨리 끝나는 강의보다 늦게 시작된다 -> 그 강의실 사용할거니까 나가게 하기
	rooms.add(course[i][1]); // 현재 강의를 더해줌.
	}
	System.out.println(rooms.size());
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub