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

11000번: 강의실 배정

---

 

• 생각

1. 강의실 시작, 끝나는 시간을 배열에 저장하여서 반복문을 돌린다. 이때 끝나는 시간을 우선순위큐(오름차순 자동 정렬)을 사용해서 맨 앞의 큐보다 해당 시작시간이 더 높은 경우에만 강의실을 배정하면 될 것 같다.

 

2. 위의 방법으로 해보니 틀렸다고 나왔다. 찾아보니 강의실 시작시간 순서대로 배열을 정렬을 해줘야된다...!

 

 

• 생각대로 했을 때의 생긴 문제점

처음 강의실 시작시간 정렬을 해주지 않아서 삽질 좀 했다. 시작시간 순서대로 정렬을 해준 뒤 강의실 사용 시작 시간과 종료 시간을 통해 강의실 최소개수를 찾았다. 

 

 

• 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[][] room;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(FindMinValue());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		room = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			room[i][0] = Integer.parseInt(st.nextToken());
			room[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 2차원 배열 정렬
        Arrays.sort(room, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int result = o1[0] - o2[0];
                if (result != 0) return result;
                return o1[1] - o2[1];
            }
        });
	}

	private static int FindMinValue() {
		PriorityQueue<Integer> queue = new PriorityQueue<>();

		queue.offer(room[0][1]);
		for(int i=1;i<N;i++) {
			if(room[i][0] < queue.peek()) {
				queue.offer(room[i][1]);
			}else {
				queue.poll();
				queue.offer(room[i][1]);
			}
		}

		return queue.size();
	}
}