백준 11000번 : 강의실 배정 java

이 문제는 우선순위 큐를 이용하여 강의실의 필요 개수를 찾아내는 문제입니다.

이 문제를 해결하기 위해서는 우선 입력받은 값들을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다.

만약 시작 시간이 같을 경우 종료 시간이 빠른 데이터 값을 앞에 둡니다.

그리고 가장 시작 시간이 빠른 데이터의 종료 시간을 우선순위 큐에 넣습니다.

그 후 다음 데이터 값의 시작 시간이 우선 순위우선순위 큐에 처음 들어있는 값보다 작다면 이 데이터의 종료 시간을 우선순위 큐에 넣습니다.

만약 시작 시간이 우선 순위 큐에 처음 들어 있는 값보다 작다면 우선순위 큐를 poll 해주고 새로운 데이터의 종료 시간을 우선순위 큐에 넣어줍니다.

위와 같이 하는 이유는 기본적으로 시작 시간을 기준으로 정렬하였기 때문에 우선 순위 큐에 들어 있는 값들의 시작 시간은 그다음에 오는 값들보다 빠릅니다.

이때 새로운 데이터의 시작 시간이 우선 순위 큐에 들어 있는 이전에 강의실을 사용하고 있던 사람의 종료 시간보다 빠르다면 사용 시간이 겹쳐 이 강의실을 같이 쓸 수 없습니다.

따라서 우선 순위 큐에 이 강의실의 종료 시간을 offer 해주어 새로운 강의실을 할당해줍니다.

그리고 만약 새로운 데이터의 시작 시간이 우선 순위 큐에 들어 있는 이전에 강의실을 사용하고 있던 사람의 종료 시간과 같거나 느리다면 이 강의실을 같이 쓸 수 있습니다.

따라서 이전에 쓰던 사람이 강의실을 다 사용하였으므로 우선순위 큐를 poll 해주고 이 강의실을 이제 새로운 사람이 사용할 것이기 때문에 이 사람의 종료 시간을 offer 해줍니다.

우선순위 큐를 이용한 이유는 종료 시간을 기준으로 정렬하여 종료 시간이 빠른 강의실 순으로 정렬하기 위함입니다.

위에 설명드린 대로 코드를 만들어보겠습니다.

---

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());

        List<Node> l = new ArrayList<>();

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            l.add(new Node(A, B));
        }

        Collections.sort(l);

        Queue<Integer> q = new PriorityQueue<>();
        q.offer(l.get(0).end);

        for(int i = 1; i<N; i++){
            Node next = l.get(i);

            if(next.start < q.peek())
                q.offer(next.end);
            else{
                q.poll();
                q.offer(next.end);
            }
        }

        System.out.println(q.size());
    }
}
class Node implements Comparable<Node>{
    int start, end;

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

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

다음과 같이 이 문제를 해결하실 수 있습니다.