백준 11000

 

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

11000번: 강의실 배정

그리디 알고리즘. 

강의 시작 순서대로 담을 우선순위 큐 하나, 강의 끝나는 시간들만 담아둘 우선순위 큐 rooms하나 이렇게 정의했다.

rooms에는 강의 끝나는 시간을 담아두고, rooms.peek(), 즉 가장 일찍 끝나는 강의실의 강의 종료 시점이 다음에 들어올 강의의 시작 시점보다 빠르거나 같은 경우에만 rooms.poll()을 수행하고, 새로 들어온 강의의 끝나는 시점을 다시 rooms에 넣으면 된다.

최종적으로 rooms의 사이즈가 필요한 강의실 개수가 된다. 

import java.util.*;
import java.io.*;
public class p11000 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> pq = new PriorityQueue<>(Comparator.comparingInt(l -> l.start));
        PriorityQueue<Integer> rooms = new PriorityQueue<>();;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            pq.add(new Lecture(start, end));
        }

        while (!pq.isEmpty()) {
            Lecture lecture = pq.poll();
            if (!rooms.isEmpty() && rooms.peek() <= lecture.start) {
                rooms.poll();
            }
            rooms.add(lecture.end);
        }
        System.out.println(rooms.size());
    }

    static class Lecture {
        int start;
        int end;

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