BOJ_11000_강의실배정

걸린 시간: 30m

알고리즘 분류: greedy

앞서 풀었던 문제와 유사한 유형의 문제입니다. 일단 강의들의 시작시간으로 정렬을 한 후 우선순위 큐(최소 힙) 을 통하여 각 강의들의 시작시간, 종료시간을 비교하여 강의실의 개수를 출력하게 됩니다.

package BOJ_11000_강의실배정;
import java.util.*;

public class Main {
    public static class Lecture{
        int start;
        int end;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        List<Lecture> lectures = new ArrayList<>();

        for(int i = 0 ; i < N; i++){
            lectures.add(new Lecture(sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(lectures, (s1, s2) ->  s1.start - s2.start);

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(Lecture lecture : lectures){
            if(!pq.isEmpty()&& pq.peek() <= lecture.start){
                pq.poll();
            }
            pq.offer(lecture.end);
        }
        System.out.println(pq.size());
    }
}