강의실 배정 - 11000

문제

//입력
3
1 3
2 4
3 5

//출력
2

풀이

import java.util.*;

// 백준 - 강의실 배정 - G5
class Dot implements Comparable<Dot> {
    int st;
    int et;

    public Dot(int st, int et) {
        this.st = st;
        this.et = et;
    }
    @Override
    public int compareTo(Dot o) {
        if(this.st== o.st) return this.et - o.et;
        return this.st - o.st;
    }
}

public class ex11000 {
    static int n;
    static ArrayList<Dot> arr = new ArrayList<>();
    static PriorityQueue<Integer> pq = new PriorityQueue<>();

    public static int solution(){
        Collections.sort(arr);

        pq.offer(arr.get(0).et);

        for(int i=1; i<n; i++){
            if(pq.peek() <= arr.get(i).st) pq.poll();
            pq.offer(arr.get(i).et);
        }
        return pq.size();
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for(int i=0; i<n; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            arr.add(new Dot(a,b));
        }
        System.out.println(solution());
    }
}

이 문제는 기본적으로 생각을 좀 하고 접근해야했다.
일단 문제에서 묻는 건 시간이 정해져있는 강의들을 하기 위해서 강의실을 몇개를 빌려야하는지 찾는 문제.

1. 우선 이런 문제는 무조건 정렬부터 시작해야한다. Comparable<객체>를 이용해서 시작시간 기준으로 정렬해준다. 그 후에 arr에 담고 Collections.sort()로 정렬.
2. 그 다음 PriorityQueue<타입>을 pq로 만들어 준다. pq를 poll하면 가장 작은값 먼저 poll한다. --> 가장 빨리 끝나는 강의실 우선 배출을 위해서.
3. 첫 강의의 et를 pq에 담아놓고 그 다음 강의의 st가 pq.peek() 즉 가장 빨리 끝나는 강의보다 크거나 같으면 가장 빨리 끝나는 et --> pq.poll을 이용해 빼준다. 그게 아니라면 그냥 또 끝나는 시간을 그냥 pq에 넣어준다 --> 이 말은 강의실을 하나 더 쓴다는 말.
4. pq의 size()를 리턴한다.