자바(백준) 11000 강의실 배정

오답 노트 & 새로 알게 된 점

이 문제는 회의실 배정이라는 문제와 같이 풀어보면 좋을 것 같다.

 

문제에서 강의실을 최소로 사용하면서 모든 강의를 해야한다고 했다.

여기서 어떻게 하면 최소로 강의실을 사용할지 생각해봤다.

 

일단 강의와 강의 사이의 간격이 좁아야한다. 

왜?

예로 1 3과 3 5을 보듯이 이렇게 이어지는 게 강의실을 최소로 사용한다고 생각했다.

그래서 시작시간을 기준으로 정렬을 한다.

 

이 때, 종료시간은 우선순위 큐에 넣는다.

이렇게 하기 위해서는 제일 처음에 있는 강의의 종료시간을 우선순위 큐에 미리 넣는다.

 

그래서 다음 강의 시작시간이 큐의 제일 앞에 있는 숫자(강의가 가장 빨리 끝나는 시간)과 

비교하여

시작시간 >= 큐.peek이면

큐에 있던 수업을 poll하고 현재 강의의 종료시간을 넣어주게 된다

-> 이 말은 즉, 그 강의실에서 이어서 수업을 한다는 뜻이다.

 

그렇다면 강의 시간을 담은 배열 A를 모두 탐색한 뒤, 

우선 순위 큐의 size가 필요한 강의실이 된다.

 

 

회의실 배정 vs 강의실 배정

 

회의실 배정은 한 회의장에서 최대한 많은 회의를 한다고 했다.

즉, 회의들이 최대한 빨리 빨리 끝나야 최대한 많은 회의를 할 수 있다.

그래서 회의 끝나는 시간으로 정렬을 하여 문제를 해결했다.

 

강의실 배정 문제는 최대한 한 강의실에서 강의를 많이 진행해야한다.

강의와 강의 사이의 텀을 최대한 줄이면서,

시작 시간을 최대한 맞추면서 한 강의실에서 강의를 진행해야함.

시작시간이 빠른 강의 부터 강의실을 사용해야 시간 낭비가 없어진다.

그래서 시작 시간으로 정렬을 하여 문제를 해결했다.

---

코드

package Greedy;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static Subject A[];
    static PriorityQueue<Integer> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        A = new Subject[N];
 
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = atoi(st.nextToken());
            int end = atoi(st.nextToken());
            A[i] = new Subject(start, end);
        }
 
        Arrays.sort(A);
 
        pro();
 
    }
 
    static void pro() {
        pq.offer(A[0].ed);
 
        for (int i = 1; i < N; i++) {
            if (A[i].st >= pq.peek()) {
                pq.poll();
            }
            pq.offer(A[i].ed);
        }
 
        System.out.println(pq.size());
    }
 
    static class Subject implements Comparable<Subject>{
        int st, ed;
 
        public Subject(int st, int ed) {
            this.st = st;
            this.ed = ed;
        }
 
        @Override
        public int compareTo(Subject o) {
            return this.st - o.st;
        }
    }
}