[백준] 1374번. 강의실 배정(JAVA)

문제

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

---

풀이(20분)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Lecture[] arr = new Lecture[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            st.nextToken();
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            arr[i] = new Lecture(start, end);
        }
        Arrays.sort(arr, (o1, o2) -> o1.start - o2.start); // 시작 시간으로 비교
        PriorityQueue<Lecture> pq = new PriorityQueue<>(); // 우선순위 큐
        pq.add(arr[0]);
        for (int i = 1; i < n; i++) {
            Lecture current = pq.peek();
            if (current.end <= arr[i].start) {
                pq.poll();
                current.end = arr[i].end;
                pq.add(current);
            } else {
                pq.add(arr[i]);
            }

        }
        System.out.println(pq.size());

    }


    public static class Lecture implements Comparable<Lecture> { // 강의
        int start;
        int end;

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

        @Override
        public int compareTo(Lecture o) {
            if (this.end == o.end) return this.start - o.start;
            return this.end - o.end;
        }
    }

}

---

문제 풀이 전략

 

시작 시간 순으로, 시작시간이 같다면 끝나는 시간이 빠른 순으로 정렬한다.

 

이후, 시작시간에 대해 시작하고, 강의가 끝나기 전에 새로 뽑은 강의가 종료 시간보다 빠르다면 큐에 넣는 방식으로 진행한다.

대표적인 그리디 문제이기 때문에 꼭 알아두도록 하자!