백준-1931번/회의실 배정 (java)

 

문제 이해

 

N개의 회의 시작시간, 끝나는 시간이 주어질때  각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구해주면 된다.

 

이 문제에서 가장 중요한 점은 각 회의들의 종료 시간이 빠른 순으로 정렬을 해야한다는 점이다.

왜냐하면 종료시간 기준으로 오름차순 정렬을 해주면 회의가 빨리 끝나서 최대한 많은 회의를 진행하는 경우를 구할 수 있기 때문이다.

 

 

문제 해결

 

ex) 예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

 

이것을 종료시간 기준 오름 차순으로 정렬해주면 다음과 같이 변한다.

[1, 4]
[3, 5]
[0, 6]
[5, 7]
[3, 8]
[5, 9]
[6, 10]
[8, 11]
[8, 12]
[2, 13]
[12, 14]

 

1에 시작 ---> 4에 종료

.

.  4보다 크면서 가장 작은 시작 시간

.

5에 시작 ---> 7에 종료

.

. 7보다 크면서 가장 작은 시작 시간

.

8에 시작 ---> 11에 종료

.

. 11보다 크면서 가장 작은 시작 시간

.

12에 시작 ---> 14에 종료

 

 

총 회의 진행 횟수 4회

 

이를 구현한 코드는 다음과 같다.

 

<전체 코드>

import java.util.Arrays;
import java.util.Scanner;

public class Problem1931 {
    static int[][] arr;
    static int N;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N=scanner.nextInt();

        arr=new int[N][2];

        for(int i=0; i<N; i++){
            for(int j=0; j<2; j++){
                arr[i][j]=scanner.nextInt();
            }
        }

        Arrays.sort(arr, (o1, o2) -> {
            if(o1[1] == o2[1]) { //종료시간이 같을 경우 시작 시간이 빠른 순
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });

        int count=0;
        int end=0;

        for(int i=0; i<N; i++){
            if(end<=arr[i][0]){
                end=arr[i][1];
                count++;
            }
        }

        System.out.println(count);
    }

}