(알고리즘)백준 11000 java 자바

원종식·2022년 7월 20일

문제

백준 11000 강의실 배정 : https://www.acmicpc.net/problem/11000

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

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

예제입력

3
1 3
2 4
3 5

예제출력

풀이

해당 문제는 그리디 + 최소 힙으로 풀었다. 먼저 강의실을 강의 시작 순서로 정렬을 한다.
그 다음 최소 힙을 활용해서 푼다. 최소 힙에 들어가는 값은 강의가 끝나는 시간이다.
최소힙의 top값이 지금 넣어야 하는 강의의 시작시간보다 작다면 해당 값을 pop하고 넣어야 할 강의의 종료시간을 최소 힙에 넣어준다. 이때는 강의가 끝나고 강의를 듣는 것이기에 강의실이 더 필요하지 않는다.
하지만 반대로 최소힙의 top값이 넣어야 하는 강의이 시작시간보다 크다면 새로운 강의실을 찾아야 하니 ans값을 1개 추가해준다. 어렵지 않은 개념이다. 최소힙을 아느냐 모르느냐가 핵심 문제!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Boj11000 {


    static class Class implements Comparable{
        public int start;
        public int end;
        public Class(int i, int j){
            this.start=i;
            this.end=j;
        }
        @Override
        public int compareTo(Object o){
            Class c=(Class)o;
            return this.start-c.start;
        }
    }//정렬을 위해 클래스 구현
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bf.readLine());
        Class[] c = new Class[n];
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();//프라이오리티 큐생성 이때 Collections.reverse()를 주면 최대힙이 된다.
        int ans=0;
        for(int i=0;i<n;i++){
            StringTokenizer st=new StringTokenizer(bf.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            c[i]=new Class(a,b);
        }
        Arrays.sort(c);//시작시간 기준 정렬
        for(int i=0;i<n;i++){
            if(pq.isEmpty()){//맨처음이면
                ans++;//첫 강의실 사용
                pq.add(c[i].end);//강의 종료시간을 최소힙에 넣어준다
            }
            else{
                if(pq.peek()<=c[i].start){//가장 최근에 끝나는 강의가 지금 강의 시작보다 작으면
                    pq.poll();//끝난 강의시간을 빼주고
                    pq.add(c[i].end);//해당 강의의 종료시간을 넣어준다
                }
                else{//만약 가장 빨리 끝나는 강의가 지금 강의 시작보다 늦다면
                    ans++;//새로운 강의실을 잡고
                    pq.add(c[i].end);//최소힙에 강의 종료 시간을 넣어준다
                }
            }
        }
        System.out.println(ans);
    }

}