[BOJ_11000] 강의실 배정

설명

---

이 전 강의실을 빼는 형태로 구현하기 위해서 PriorityQueue 내부에서는 가장 먼저 들어간 강의실을 빼는 형태로 생각하고 진행을 하였으며 이때, 새로 들어오는 강의가 이전 강의의 end 시간 보다 start 시간이 크면 PriorityQueue의 새로운 엔드포인트로 생성이 되는 것으로 생각하고 PriorityQueue를 늘리고 이런 경우가 아니고 만일, 들어오는 강의가 이전 강의의 end 시간 보다 start 시간이 작으면 이때는 강의실을 늘리지 않아도 되는 경우이므로 현재 내가 보는 강의실은 끝나는 엔드포인트로 지정하고 지금 들어온 강의를 PQ에 넣어서 상태값을 조정했습니다.

 

그러나, 이 모든 경우는 앞서 Arrays.sort를 통해서 강의의 순서값이 정렬이 되어 있어야 이전 상태 값이 다음 나오는 강의가 뒤에 후행으로 따라오는 강의 값인 것을 보장 해주므로 먼저 선제로 정렬 후 PriorityQueue 사용하여서 문제를 풀어야 합니다. 

 

코드

---

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_11000 {
    static class Lecture implements Comparable<Lecture>{
        int start, end;
        public Lecture(int start, int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Lecture o) {
            if(this.start == o.start) return this.end - o.end;
            else return this.start - o.start;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        Lecture[] lectures = new Lecture[N];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(in.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lectures[i] = new Lecture(start, end);
        }
        Arrays.sort(lectures);
        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());
    }
}

 

11000번: 강의실 배정