강의실 배정

https://www.acmicpc.net/problem/11000

풀이

이전에 풀었던 회의실 배정과 유사하게 그리드 알고리즘을 이용해서 풀이했다.

먼저 인풋으로 들어온 값들을 수업 시작시간 기준으로 오름차순으로 정렬한 뒤 우선순위 큐에는 강의가 끝나는 시간을 넣는다.

우선 순위 큐에 넣을 때 넣으려는 강의의 시작시간이 큐의 제일 앞의 값보다 작으면 우선 순위 큐에 강의가 끝나는 시간을 넣고 크거나 같다면 큐의 제일 앞의 값을 제거하고 넣으려는 강의의 끝나는 시간을 큐에 넣는다.

이 과정이 끝나고 큐의 사이즈가 강의실 개수가 되어 답이된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static int n, m, k;
    static int[] alpha;
    static String[] ins;
    static int max = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //String[] input = br.readLine().split(" ");
        n = Integer.parseInt(br.readLine());

        ArrayList<Pair> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            int s = Integer.parseInt(line[0]);
            int e = Integer.parseInt(line[1]);
            list.add(new Pair(s, e));
        }

        list.sort(Pair::compareTo);

        //큐의 최상단과 비교해서 시작시간이 끝나는 시간보다 작으면 큐에 푸시하고 크면 최상단을 제거후 푸시?
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(list.get(0).end);
        for (int i = 1; i < list.size(); i++) {
            Integer top = pq.peek();
            Pair in = list.get(i);
            if (top <= in.start) {
                pq.poll();
            }
            pq.offer(in.end);
        }

        bw.write(pq.size() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Pair implements Comparable<Pair> {
    public int start;
    public int end;

    public Pair(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Pair o) {
        if (this.start < o.start)
            return -1;
        else if (this.start == o.start) {
            if (this.end < o.end)
                return - 1;
            else
                return 1;
        } else
            return 1;
        //return Integer.compare(this.start, o.start);
    }
}