[백준 11000] 강의실 배정

 

회의실배정 문제와 유사한데 조금 더 꼬아낸 문제다.

 

모든 수업이 가능해야 하므로 배열 정렬은 시작 시간에 대해 오름차순으로 정렬한다.

진행중이던 강의가 끝나면 그 강의실을 재사용할 수 있으므로 강의 정보를 담을 자료구조가 필요하다.

처음에는 큐를 이용하여 풀었는데 큐에서도 끝나는 시간이 빠른것을 우선으로 비교해야 하므로

우선순위 큐로 구현했다.

 

진행은 다음과 같다.

1. 강의 정보를 시작 시간에 따라 오름차순으로 정렬한다.

2. 강의 종료 시간을 우선순위 큐에 담는다.

3. 큐의 front 와 현재 강의 정보의 시작시간과 비교하여 시작시간이 크거나 같다면 큐를 pop 한다.

   (강의실이 비었다)

4. 마지막에 큐의 개수를 센다.

 

강의 정보를 구조체나 클래스로 구현하여도 되지만 회의실배정 때 소스를 끌어다가 고쳤기 때문에

그냥 배열로 풀었다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[][] = new int[n][2];
        
        for(int i=0; i<n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        
        Arrays.sort(a, new Comparator<int[]>() {
           public int compare(int start[], int end[]) {
               if(start[0] == end[0])
                   return start[1] - end[1];
               return start[0] - end[0];
           }
        });
        
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        
        for(int i=0; i<n; i++) {
            int end = a[i][1];
            if(!q.isEmpty() && q.peek() <= a[i][0])
                q.poll();
            q.offer(end);
        }
        System.out.println(q.size());
    }
}