[Java] 백준 1374번 : 강의실

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

1374번: 강의실

---

💡 문제 풀이

강의실 배정 문제이다. 이 문제는 최선의 강의실 개수를 구하는 문제이다.

가장 빨리 끝나는 강의 혹은 가장 빨리 시작하는 강의를 기준으로 탐색해서 해결할 수 있다.

이번 문제에선 가장 빨리 시작하는 강의를 기준으로 해결했다.

 

대기 중인 강의가 우선순위 큐에 저장되고 강의의 개수만큼 탐색한다.

지금 하는 강의가 끝나고 대기 중인 다음 강의가 진행될 수 있다면 다음 강의를 대기 중에서 제외한다.

진행될 수 없다면 큐에 넣고(추가적인 강의실을 확보한다), 다른 강의와의 매핑을 대기한다.

 

확인하는 강의에 따라 큐에 남아있는 강의 수가 적어진다. 

대기 중인 강의가 최대인 값이 최대로 필요한 강의실의 개수이다.

✔️ 느낀 점

다른 유형인 가장 많은 활동을 선택하는 경우는 코드를 짜는 게 편했으나, 이 경우에서는 어려웠다.

처음에는 우선 순위큐를 두 개 두고 인덱스를 활용하는 방법으로 코드를 짰으나 시간 초과가 발생했다. 

다음 경우를 찾기 어려워서 다른 코드를 참고했다. 자바는 어렵다 ㅎㅎ

💻 코드

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

public class _1374 {
    static class Lesson implements Comparable<Lesson> {
        private final int start;
        private final int end;

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

        public static Lesson from(StringTokenizer st) {
            return new Lesson(nextToken(st), nextToken(st));
        }

        public int getStart() {
            return start;
        }

        public int getEnd() {
            return end;
        }

        @Override
        public int compareTo(Lesson o) {
            return this.start - o.getStart();
        }
    }

    static BufferedReader br = getBufferedReader();
    static StringTokenizer st;
    static Queue<Integer> endTimes = new PriorityQueue<>();
    static List<Lesson> lessons = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        int n = readInput();
        initInput(n);
        int rooms = countRooms(n);
        System.out.println(rooms);
    }

    private static int countRooms(int n) {
        int count = 0;

        for (int i = 0 ; i < n ; i++) {
            Lesson nextLesson = lessons.get(i);
            while (isNotEmptyQueue() && isNextStartGE(nextLesson)) {
                endTimes.poll();
            }
            endTimes.add(nextLesson.getEnd());
            count = Math.max(count, endTimes.size());
        }

        return count;
    }

    private static boolean isNextStartGE(Lesson nextLesson) {
        return endTimes.peek() <= nextLesson.getStart();
    }

    private static boolean isNotEmptyQueue() {
        return !endTimes.isEmpty();
    }

    private static void initInput(int n) throws IOException {
        for (int i = 0 ; i < n ; i++) {
            st = getTokenizer();
            nextToken(st);
            lessons.add(Lesson.from(st));
        }

        Collections.sort(lessons);
    }

    private static int nextToken(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }

    private static int readInput() throws IOException {
        return Integer.parseInt(br.readLine());
    }

    private static StringTokenizer getTokenizer() throws IOException {
        return new StringTokenizer(br.readLine());
    }

    private static BufferedReader getBufferedReader() {
        return new BufferedReader(new InputStreamReader(System.in));
    }
}