[BOJ 11000] 강의실 배정

[BOJ 11000] 강의실 배정

 

1. 문제 : https://www.acmicpc.net/problem/11000

 

2. 풀이

정렬 + 우선순위 큐 합친 문제

끝나는 시간이 적은 순서대로 peek 해야하기 때문에 우선순위 큐

* poll말고 peek 써도됨...!

 

3. 코드

import java.util.*;

public class Main {
    static int N;
    static int cnt = 0;
    static int arr[][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] obj1, int[] obj2) {
                if(obj1[0] == obj2[0]) return obj1[1] - obj2[1];
                else return obj1[0]-obj2[0];
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(arr[0][1]);
        cnt++;

        int now;
        int next;
        int nextEnd;
        for(int i=1; i<arr.length; i++){
            now = pq.poll();
            next = arr[i][0];
            nextEnd = arr[i][1];

            if(next < now) {
                pq.add(now);
                cnt++;
            }

            pq.add(nextEnd);
        }
        System.out.println(cnt);
    }
}

 

유사문제 - 최소 회의실 개수 https://www.acmicpc.net/problem/19598

package baekjoon;

import java.util.*;

public class Main {
    static int N;
    static int arr[][];
    static int cnt;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        arr = new int[N][2];

        for(int i=0; i<N; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] > o2[0]){
                    return 1;
                } else if(o1[0] == o2[0]){
                    if(o1[1] > o2[1]) return 1;
                    else return -1;
                } else {
                    return -1;
                }
            }
        });


        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(arr[0][1]);
        cnt++;

        int k=1;

        while(true){
            if(k>=N) break;
            if(pq.peek() > arr[k][0]){
                cnt++;
            }else{
                pq.poll();
            }
            pq.offer(arr[k][1]);
            k++;
        }

        System.out.println(cnt);
    }

}