boj 11000 강의실 배정

www.acmicpc.net/problem/11000

11000번: 강의실 배정

N개의 수업이 주어지면 강의실을 최소로 사용해서 모든 수업을 해야합니다.

저는 강의 시작시간 기준으로 정렬하였고, 우선순위 큐에 강의 종료시간을 넣었습니다.

 

q.peek()은 현재 진행중인 강의 중 가장 빠르게끝나는 강의이며, 다음 진행할 강의와 비교를 합니다 (x <= list[i][0])

x <= list[i][0]이면 같은 강의실에서 강의를 할 수 있으므로 remove를 해줍니다.

강의는 무조건 해야하므로 마지막에 끝나는 시간을 add 해줍니다.

마지막으로 q의 크기를 출력하시면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int N;
 
    static void func() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(list[0][1]);
        for (int i = 1; i < N; i++) {
            int x = q.peek();
 
            if (x <= list[i][0])
                q.remove();
            q.add(list[i][1]);
        }
 
        System.out.println(q.size());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0])
                    return a[1] - b[1];
                else
                    return a[0] - b[0];
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}