링크

11000 강의실 배정

문제

풀이

처음에 회의실 배정과 비슷한 유형이라 정렬까지는 생각했다.
정렬까지는 생각했다. 근데 시작점과 끝나는점 둘다 오름차순으로 정렬하고 그 다음에는 못풀어서 사람들 블로그 봤다. 우선순위 큐를 강의장 방이라고 생각하면 된다.
끝나는 점을 기준으로 우선순위 큐를 넣고 강의시간마다 꺼내서 큐에 꺼낸 요소와 강의 시작시간과 비교한다.
그리고 만약 현재 강의 종료 시간이 큐에서 꺼낸것보다 이르면 큐에 요소를 추가해 강의장 방을 추가한다고 생각하면 된다.

예제 처럼
3
1 3
2 4
3 5
가 있다면 정렬(시작점, 도착점 오름차순)해서 list에 넣었다.
1. 1 3
이 경우 큐가 비어있기 때문에 그냥 끝나는시간 3을 넣어준다.

2. 2 4
   큐에서 peek한 값이 3이고 강의가 시작하는 시간이 2이기 때문에 3(queue.peek()) > 2(element.start)이기 때문에 강의장을 하나 더 열어야 한다. 그래서 큐에다가 4를 넣어준다.

3. 3 5
   큐에서 peek한 값이 3이고 강의가 시작하는 시간이 3이기 때문에 3(queue.peek()) == 3(element.start)이기 때문에 강의장을 하나 더 안열어도 된다.
   위와 같이 같거나 3 5가 아닌 4 5라도 강의장을 안열어도 되기 때문에 queue.peek() <= element.start인 경우는 queue에서 요소를 하나 없애주면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Node implements Comparable<Node>{
    int start;
    int end;

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

    @Override
    public int compareTo(Node node){
        if(this.start == node.start){
            return this.end - node.end;
        }

        return this.start - node.start;

    }
}

public class Main{

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        List<Node> list = new ArrayList<>();

        for(int i=0;i<n;i++){
            String[] arr = br.readLine().split(" ");
            int start = Integer.parseInt(arr[0]);
            int end = Integer.parseInt(arr[1]);

            list.add(new Node(start, end));
        }

        Collections.sort(list);

//        for(Node element : list){
//            System.out.println(element.start + " " + element.end);
//        }

        //강의실에 배정된 끝나는 시간 저장
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return o1 - o2;
        });

        for(int i=0;i<list.size();i++){
            if(!pq.isEmpty() && pq.peek() <= list.get(i).start){
                pq.poll();
            }

            pq.add(list.get(i).end);
        }
        System.out.println(pq.size());

    }

}