[JAVA] BOJ(백준) - 강의실 배정 - 11000

문제내용

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

11000번: 강의실 배정

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

---

문제풀이

강의개수가 최대 200000이라서 완탐으로는 시간초과가 난다. ( O(N^2) )

따라서 시간을 줄일수 있는 방법이 필요한데 이를 위해서 필요한게 정렬이다.

 

먼저 시작시간을 오름차순 정렬 후 시작시간이 같다면 종료시간을 오름차순 정렬해준다.

시작 시간을 먼저 정렬해주는 이유는 시작시간이 빠른 강의 일수록 먼저 강의실을 배정하고 그뒤에 시작시간이 느린 강의들을 붙이면서 강의실의 개수를 최소화 시켜주기 위해서이다.

그리고 시작시간 이후 종료시간을 오름차순 해주는 이유는 사작시간이 느린 강의들 중 종료시간이 작은것 즉, 강의가 빨리 끝나는 것순으로 강의를 배정해서 하나의 강의실에 여러개의 강의를 들을수 있도록한다.

 

이를 구현하기 위해선 정렬 후 우선순위큐를 쓰는게 좋다.

이때, 정렬한 데이터를 첫번째부터 탐색하고,

탐색한 강의의 시작시간 = start / 우선순위 큐의 peek값 = 종료시간 = end 라고 할때,

"end > start" 일때는 우선순위 큐에 현재 탐색한 강의의 종료시간을 add

"end <= start" 일때는 poll()한뒤 현재 탐색한 강의의 종료시간을 add 시켜 줌으로써 해당 강의실의 마지막 강의 종료시간을 갱신시켜준다.

 

정렬된 데이터를 한번 순회하면서 이과정을 거치고 우선순위 큐에 남은 데이터의 개수가 곧 강의실의 개수가 된다.

 

---

코드

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

public class Main {
	static class Time{
		int s, e;
		public Time(int s, int e) {
			this.s = s;
			this.e = e;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		List<Time> list = new ArrayList<Time>();
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s=Integer.parseInt(st.nextToken()), e=Integer.parseInt(st.nextToken());
			list.add(new Time(s, e));
		}
		
		//정렬(시작시간 오름차순 먼저 -> 이후에 종료시간 오름차순)
		Collections.sort(list, new Comparator<Time>() {
			@Override
			public int compare(Time o1, Time o2) {
				int s1=o1.s, s2=o2.s;
				if(s1>s2) return 1;
				else if(s1<s2) return -1;
				else {
					int e1=o1.e, e2=o2.e;
					if(e1>e2) return 1;
					else if(e1<e2) return -1;
					else return 0;
				}
			}
		});
		
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		pq.add(list.get(0).e);
		for(int i=1; i<list.size(); i++) {
			Time time = list.get(i);
			int end = pq.peek();
			if(end<=time.s) {//기존 강의실에 새로운 강의를 붙일수 있을 경우
				pq.poll();
				pq.add(time.e);
			}else pq.add(time.e); //새 강의실 배정해야할 경우
		}
		
		System.out.println(pq.size());
	}
}

---

마치며

최근 정렬 문제를 풀때 O(N^2)으로 풀면 시간초과가 나는 문제들이 자주나온다.

다양한 풀이법을 생각해내는 사고가 필요하다.