[그리디] 백준 11000번 강의실 배정(Java)

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

📚 문제

Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

 

📝 문제 해결

1)  입력받은 강의 시간을 오름차순으로 정렬해준다.

    시작시간이 같을 경우 종료시간을 기준으로 오름차순 정렬

2-1) 우선순위 큐에 시작시간이 가장 빠른 강의의 종료시간(배열의 첫번째 end값)을 저장한 뒤

2-2) 현재 탐색하는 강의의 시작시간이 큐에 담겨져있는 강의들 중 가장 빠른 종료시간보다 크거나 같은 경우 강의실로 배정해준다. 

3) 순회하면서 현재 탐색하는 강의의 종료시간을 새로 우선순위 큐에 넣어준다.

4) 모든 탐색이 끝난 후 현재 남아있는 큐의 사이즈(강의실 배정 개수)를 출력해준다.

 

💻 코드

import java.util.*;

public class BOJ11000 {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[][] arr = new int[n][2];
		for(int i = 0; i < n; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}

		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		
        PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.add(arr[0][1]);
		
		for(int i = 1; i < n; i++) {
			if(pq.peek() <= arr[i][0]) pq.poll();
			
			pq.add(arr[i][1]);
		}
		
		System.out.println(pq.size());
	}
}

💡 오름차순 Arrays.sort()가 아닌 내림차순이 이나 원하는대로 정렬 조건을 달리 하려면 Comparable인터페이스의 compareTo()메서드를 원하는 조건으로 오버라이드하거나 익명인터페이스 java.util.Comparator를 구현한 Class내compare()메서드를  원하는 정렬조건으로 오버라이드하여 sort 메서드 호출시 구현한 Comparator 클래스를 명시해 주면 된다. -> new Comparator를 선언하고  compare 함수 부분을 수정해주면 된다.

Arrays.sort(arr, new Comparator<int[]>() {
    public int compare(int[] o1, int[] o2) {
        if(o1[0] == o2[0]) return o1[1] - o2[1];
        return o1[0] - o2[0];
    }
});

 

[출처 : https://ifuwanna.tistory.com/232]