[BAEKJOON] 11000 강의실배정 (Java)

[ 문제 ]

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

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

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

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

입력

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

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

출력

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

[ 핵심풀이 ]

강의의 시작시간과 종료시간이 중점적인 요소다.

1) 시작시간이 최소 종료시간보다 크다면, 그 강의는 따로진행되야하므로 큐에 넣어준다.

2) 시작시간이 최소 종료시간보다 작거나 같으면, 그강의가 끝난 자리에서 진행이가능하므로

큐의 최소종료시간을 삭제하고 이 강의의 종료시간을 삽입한다.

3) 모든강의에대해서 판별한 뒤 큐에 남아있는 종료시간의 개수가 사용한 강의실의 개수이다.

4) 우선순위 큐를사용해서 간단하게 했지만, 굳이 안쓰고 1931처럼 풀어도 될 것 같긴하다.

[ Java ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class xy_11000 implements Comparable<xy_11000>{
    int fs;
    int se;
    xy_11000(int fs, int se){
        this.fs=fs;
        this.se=se;
    }
    public int getFs() {
        return fs;
    }
    public void setFs(int fs) {
        this.fs = fs;
    }
    public int getSe() {
        return se;
    }
    public void setSe(int se) {
        this.se = se;
    }
    @Override
    public int compareTo(xy_11000 o) {
        if (this.fs > o.getFs())
            return 1;
        else if (this.fs < o.getFs())
            return -1;
        else {
            if (this.se >= o.getSe())
                return 1;
            else if(this.se < o.getSe())
                return -1;
        }
        return 0;
    }
}
public class _11000_강의실배정 {
    static PriorityQueue<xy_11000>pq = new PriorityQueue<xy_11000>();
    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int tc = Integer.parseInt(st.nextToken());
        for(int t=1;t<=tc;t++) {
            st = new StringTokenizer(br.readLine());
            int fs = Integer.parseInt(st.nextToken());
            int se = Integer.parseInt(st.nextToken());
            pq.add(new xy_11000(fs, se));
        }
    }
    static void solve() {
        PriorityQueue<Integer>q = new PriorityQueue<Integer>();
        while(!pq.isEmpty()) {
            xy_11000 out = pq.poll();
            int fs = out.getFs();
            int se = out.getSe();
            if (q.isEmpty()) {
                q.add(se);
                continue;
            }
            if (q.peek() > fs)
                q.add(se);
            else {
                q.poll();
                q.add(se);
            }
        }
        System.out.println(q.size());
    }
    public static void main(String[] args) throws IOException {
        init();
        solve();
    }
}