[백준, G5, 그리디] 강의실 배정

0. 문제 링크

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

11000번: 강의실 배정

---

1. 문제 핵심

1. N개의 강의가 주어지는데 최소한의 강의실을 사용해 모든 수업을 가능케 해야한다.
2. 강의실은 수업이 끝난 직후, 다른 강의실을 사용할 수 있기 때문에 1개 이상의 강의실이 사용될 수 있다.

 

---

2. 문제 접근

1. 그리디한 문제임을 알고 있었기 때문에 처음에 수업이 시작하는 순 => 수업이 마치는 순으로 정렬을 해주었습니다.
2. 다만 그 이후에 최소한으로 강의실을 사용하기 위해 정렬한 강의 시간을 어떻게 활용해야할지 감이 잡히지 않았습니다.
3. 1시간 30분 뒤, 솔루션을 조금 참고했고 2개의 PQ가 필요하단 문장으로 바로 감을 잡았습니다.
4. 먼저 넣어준 PQ는 강의 시간 관리를, 나머지 PQ는 강의실을 관리해준다고 생각하면 이해가 쉽게 될 것입니다.
5. 강의 시간 PQ는 시작 시간과 끝 시간을 오름차순으로 정렬해주고 하나씩 꺼내준 것을 강의실 PQ에 넣어주어 끝 시간을 오름차순으로 관리해줍니다.
6-1. 강의 시간 PQ에서 꺼낸 강의 시간의 시작 시간보다 일찍 끝난 강의실이 있는지 PQ에서 확인해주고 있다면 해당 강의실에 해당 강의를 넣어줍니다.
6-2. 만약 어떤 강의실도 끝나지 않았다면 해당 강의를 위해 새로운 강의실을 배정해주기 위해 강의 시간 PQ에서 강의실 PQ로 강의를 옮겨줍니다.
7. 이런 방식으로 작업을 수행하게 되면 강의실 PQ에 남아있는 갯수만큼 강의실이 필요함을 알게 됩니다. 

그림 1.

 

---

3. 코드 분석

두개의 PQ를 생성해줍니다. 강의 PQ는 시작, 끝 모두 오름차순 정렬해주고 강의실 PQ는 끝 시간만 오름차순 정렬해줍니다.

시작과 끝 정보를 입력받습니다.

 

하나씩 꺼내면서 강의 시작 시간과 강의실 끝 시간을 비교해줍니다.

 

---

4. 베스트 코드 분석

 

---

5. 코드

import java.util.*;
import java.io.*;

public class Main {
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

//    public static void main(String[] args) throws IOException
//    {
//        Reader s=new Reader();
//        int n = s.nextInt();
//        int k = s.nextInt();
//        int count=0;
//        while (n-- > 0)
//        {
//            int x = s.nextInt();
//            if (x%k == 0)
//                count++;
//        }
//        System.out.println(count);
//    }

    // 종료 시간 순으로 넣어야 함
    // 특정 시작 시간이 들어왔을 때 이전에 끝나는 강의실이 있다면 그곳에 넣으면 됨.
    // 강의실이 없다면 새 강의실을 파고 새로 저장
    public static void main(String[] args) throws IOException {
        Reader s = new Reader();
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
//        int N = Integer.parseInt(br.readLine());
        int N = s.nextInt();
        // 강의 시작시간이 작고 끝 시간이 작은 순서부터
        PriorityQueue<int[]> start = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0] == 0 ? o1[1] - o2[1] : o1[0] - o2[0] > 0 ? +1 : -1);
        // 강의 끝 시간이 작은 순부터
        PriorityQueue<int[]> end = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        int[][] room = new int[N][2];
        // 각 강의실의 타임테이블을 저장
        List<Deque<int[]>> dqList = new LinkedList<>();
        List<int[]> rooms = new LinkedList<>();
        for (int i = 0; i < N; i++) {
//            st = new StringTokenizer(br.readLine());
//            room[i][0] = Integer.parseInt(st.nextToken());
//            room[i][1] = Integer.parseInt(st.nextToken());
            room[i][0] = s.nextInt();
            room[i][1] = s.nextInt();

            start.add(new int[]{room[i][0], room[i][1]});
            rooms.add(new int[]{room[i][0], room[i][1]});
        }
        int[] crnt;
        while(!start.isEmpty()){
            //end가 없다면 하나 넣어줌
            if(end.size() == 0){
                end.add(start.poll());
            }
            crnt = start.poll();
            //가장 빠른 강의가 종료되는 강의실보다 같거나 더 늦게 끝난다면 해당 강의실 교체
            if(crnt[0] >= end.peek()[1]){
                end.poll();
                end.add(crnt);
            }
            // 종료되는 강의가 더 빨리 끝난다면
            else{
                end.add(crnt);
            }
        }
        System.out.println(end.size());

//        Map<Integer, Integer> map = new HashMap<>();

//        for(int i = 0; i < N; i++){
//            if(map.get(room[i][0]) == null){
//
//            }
//        }
//
//        Arrays.sort(room, (o1, o2) -> o1[0] - o2[0] == 0 ? o1[1] - o2[1] : o1[0] - o2[0] > 0 ? +1 : -1);
//
//                for (int i = 0; i < 4; i++) {
//            System.out.println(room[i][0] + " " + room[i][1]);
//        }
//
////         첫 강의실 입력
//        Deque<int[]> tmp = new LinkedList<>();
//        tmp.add(room[0]);
//        dqList.add(tmp);
//        List<Integer> deleteRooms = new LinkedList<>();
//        boolean isInput;
//        int answer = 0;
//        // 남은 강의 순회
//        while (rooms.size() != 0) {
//            int lastTime = 0;
//            int cnt = 0;
//            for (int[] i : rooms) {
//                // 마지막 시간보다 강의 시간이 같거나 더 늦을 때
//                if (lastTime <= i[0]) {
//                    deleteRooms.add(cnt);
//                    lastTime = i[1];
//                }
//                cnt++;
//            }
//            Collections.sort(deleteRooms, (o1, o2) -> o2 - o1);
//            // 처리된 강의는 삭제
//            for (int i : deleteRooms) {
////                System.out.println(i);
//                rooms.remove(i);
//            }
//            deleteRooms.clear();
//            answer++;
//        }
//        System.out.println(answer);

//        for (int i = 1; i < N; i++) {
//            isInput = false;
//            // 저장된 모든 강의장을 순회하며 입력 가능한지 확인
//            for (Deque<int[]> dq : dqList) {
//
//                // 각 강의실의 종료시간보다 i번째 강의 시작 시간이 같거나 더 늦는 경우
//                if (dq.peekLast()[1] <= room[i][0]) {
//                    dq.addLast(room[i]);
//                    isInput = true;
//                    break;
//                }
//            }
//            if (!isInput) {
//                tmp = new LinkedList<>();
//                tmp.add(room[i]);
//                dqList.add(tmp);
//            }
//        }
//        System.out.println(dqList.size());
    }
}