분류 : 그리디
1. 문제
https://www.acmicpc.net/problem/11000
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
2. 입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)
3. 풀이
1. 재귀함수 이용(시간 초과 발생)
DFS를 이용한 방법이다.
시간표를 강의 시작 시간이 빠른 순으로 정렬하고, 시작 시간이 같으면 끝나는 시간이 빠른 순으로 정렬
-> DFS로 첫번째 강의부터 끝나는 시간 이후로 연달아서 강의실을 쓸 수 있는 강의를 찾는다.
=> 시간초과 발생
2. Priority Queue 사용
정렬방식은 1번 방식과 똑같다.
다른점은 우선순위 큐를 이용해 강의실을 다르게 쓰는 강의들만 큐에 넣어 큐 사이즈를 통해 정답을 얻는다.
- 첫번째 강의의 끝나는 시간을 큐에 무조건 넣는다.
- 두번째 강의가 시작하는 시간과 큐의 맨 앞에 있는 강의가 끝나는 시간을 비교한다.
2-1. 큐의 맨 앞에 있는 강의가 먼저 끝나면 큐의 맨 앞 강의를 뺀다.
2-2. 방금 비교한 강의의 끝나는 시간을 큐에 넣는다.
=> 끝나는 시간을 비교해 같은 강의실을 쓸 수 있는지 확인한다.
4. 코드
1. 재귀함수
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class assignLecture {
static int N;
static int [][] classes;
static int [] check;
static int answer;
public static void solution() throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine());
//시간표 담을 배열, [시작][끝]
classes = new int[N][2];
check = new int[N];
for(int i=0;i<N;i++){
StringTokenizer st = new StringTokenizer(bf.readLine()," ");
classes[i][0] = Integer.parseInt(st.nextToken());
classes[i][1] = Integer.parseInt(st.nextToken());
}
//시작 시간이 빠른 순으로 정렬
//시작 시간이 같으면 끝나는 시간이 빠른 순으로
Arrays.sort(classes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]==o2[0]){
return o1[1] > o2[1] ? 1 : -1;
}
return o1[0] > o2[0] ? 1 : -1;
}
});
answer = N;
for(int i=0;i<N;i++){
findclass(i,classes[i][1]);
}
}
public static void findclass(int start, int end){
for(int i=start;i<N;i++){
if(classes[i][0] <= end && check[i]==0){
answer--;
check[i] = 1;
//System.out.println(answer);
findclass(start+1,classes[i][1]);
}
}
}
}
2. Priority Queue
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static void main(String args[]) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N;
int [][] classes;
N = Integer.parseInt(bf.readLine());
//시간표 담을 배열, [시작][끝]
classes = new int[N][2];
for(int i=0;i<N;i++){
StringTokenizer st = new StringTokenizer(bf.readLine()," ");
classes[i][0] = Integer.parseInt(st.nextToken());
classes[i][1] = Integer.parseInt(st.nextToken());
}
//시작 시간이 빠른 순으로 정렬
//시작 시간이 같으면 끝나는 시간이 빠른 순으로
Arrays.sort(classes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]==o2[0]){
return o1[1]-o2[1];
}
return o1[0]-o2[0];
}
});
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(classes[0][1]);
for(int i=1;i<N;i++){
if(queue.peek()<=classes[i][0]){
queue.poll();
}
queue.add(classes[i][1]);
}
System.out.println(queue.size());
}
}
기록용.