[백준] 11000: 강의실 배정 - JAVA

06 Aug 2023 in Algorithm on 자료 구조

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

풀이

수업들의 시작, 종료 시간이 주어지고 강의실을 최소로 배정해야 한다.

수업이 끝나면 해당 강의실을 사용할 수 있다.

수업에 대한 정보를 입력받아 시작 시간을 오름차순으로, 시작 시간이 같다면 종료 시간을 오름차순으로 정렬했다.

우선순위큐에 종료시간을 오름차순으로 담으면서 수업에 대한 정보를 넣어줬다.

pq.peek()이 다음 수업의 시작시간보다 작거나 같으면 pq에서 제거해주고 다음 수업을 pq에 넣었다.

pq.peek()이 없거나, 다음 수업의 시작시간보다 크다면 answer을 하나 늘려줬다.

---

메모리: 67960KB

시간: 740ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int s;
        int e;

        public Node(int s, int e) {
            this.s = s;
            this.e = e;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Node[] table = new Node[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            table[i] = new Node(s, e);
        }
        Arrays.sort(table, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.s == o2.s) {
                    return Integer.compare(o1.e, o2.e);
                } else {
                    return Integer.compare(o1.s, o2.s);
                }
            }
        });

        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            if (!pq.isEmpty() && pq.peek() <= table[i].s) {
                pq.poll();
            } else {
                ans++;
            }
            pq.offer(table[i].e);
        }

        System.out.println(ans);
    }

}