[BOJ 그리디] 강의실 1374.JAVA

문제 링크 : https://www.acmicpc.net/problem/1374
등급 : Gold IV

1374번: 강의실

문제 해설

강의의 개수가 최대 100,000개이고 강의 시간은 최대 10억이다. 이 문제는 모든 강의를 정렬하면 시간 초과가 발생하는 문제이다. 그래서 모든 강의를 정렬하지 않고 이전 강의의 끝 시간과 다음 강의의 시작 시간을 비교하여 로직을 구현한다. 아래는 로직의 순서를 나열하였다.

1. 강의의 시작 시간 순으로 정렬한다.
2. 첫 강의가 끝나고 다음 강의가 시작된다면 다음 강의를 제거한다.
3. 첫 강의가 끝나기 전에 강의가 시작된다면 강의실을 추가하고 강의실 개수를 갱신한다.
4. 2번과 3번을 모든 강의가 진행될 때까지 반복한다.

아래와 같이 소스를 공유합니다.

public class 강의실 {
    public static class Node {
        int o, s, e;
        Node(int o, int s, int e) {
            this.o = o;
            this.s = s;
            this.e = e;
        }
    }
    public static List<Node> list = new ArrayList<>();
    public static PriorityQueue<Integer> que = new PriorityQueue<>();
    public static Comparator<Node> comparator = new Comparator<>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o1.s, o2.s);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int o = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            list.add(new Node(o, s, e));
        }

        Collections.sort(list, comparator);

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++) {
            while(!que.isEmpty() && que.peek() <= list.get(i).s) {
                que.poll();
            }

            que.add(list.get(i).e);
            max = Math.max(max, que.size());
        }

        System.out.println(max);
    }
}