백준 11000번 강의실 배정

https://www.acmicpc.net/problem/11000

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

public class Main {

	static int N;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]==o2[0]) {
					return Integer.compare(o1[1], o2[1]);
				}
				return Integer.compare(o1[0], o2[0]);
			}
		});
		for (int i = 0; i <N ; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			pq.add(new int[] {a,b});
		}
		PriorityQueue<int[]> pq2 = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1]==o2[1]) {
					return Integer.compare(o1[0], o2[0]);
				}
				return Integer.compare(o1[1], o2[1]);
			}
		});
		int[] arr = pq.poll();
		pq2.add(arr);
		int count = 1;
		while(!pq.isEmpty()) {
			arr = pq.poll();
			int len = pq2.size();
			boolean flag = false;
			for (int j = 0; j < len; j++) {
				if(arr[0]>=pq2.peek()[1]) {
					pq2.poll();
					pq2.add(arr);
					flag = true;
					break;
				}
			}
			
			if(!flag) {
				//System.out.println(arr[0]+" "+arr[1]);
				pq2.add(arr);
				count++;
			}
			
		}
		System.out.println(count);
	}

}

풀이방법

우선 규칙자체를 찾는것은 그렇게 어렵지 않았다.
시작시간이 빠른 순서대로 정렬 후, 처음부터 탐색하는데, 끝나는시간<=시작시간이 되면 연달아 강의를 하는 로직을 구현하면 된다.
하지만 이렇게 수행하면 시간초과가 발생한다.
이문제의 핵심은 탐색시에 시간초과를 줄이는 것이다.

1. 우선 시작시간을 기준으로 오름차순 정렬한다.(나는 그냥 이것도 우선순위큐가 더 빠를거 같아서 우선순위 큐에 담았다.)
   🔉이때, 시작시간이 같다면 종료시간을 기준으로 오름차순한다.
   종료시간이 짧아야 이후 시작하는 강의와 연달아 될 확률이 높아지므로.
2. 이후 1에서만든 pq를 종료시간을 기준으로 만든 pq2와 비교한다.
   📢pq에서 꺼낸 시작시간 >= pq2에서 가장위에 있는 종료시간 이라면, pq2에서 해당 강의를 빼고, pq에서 꺼낸 강의를 넣어준다.(연강설정)
3. 만약 pq2를 다 뒤졌는데 할수있는 연강이 없다면, 강의실을 추가하고(count++) pq2에 넣어준다.

후기

비슷한 문제를 푼 경험이 있어서 그런가 오래걸리긴 했어도 어떻게 풀긴했다
우선순위큐도 정렬처럼 우선순위를 내가 직접 설정할 수 있다는걸 알 수 있었다.