그리디/2차배열 정렬/회의실 배정

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

1931번: 회의실 배정

package 플레가자스터디_백트래킹_BFS_DP;

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

public class bj_회의실배정_1_1931 {
    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++) {
            for (int j = 0; j < 2; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        //회의 시간이 끝나는 시간대로 오름차순 배열을 한다.
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });

        int count = 1; // 첫 번째 회의는 무조건 배정되므로 1부터 시작합니다.
        int end = arr[0][1]; // 첫 번째 회의의 끝나는 시간을 저장합니다.
        for (int i = 1; i < N; i++) {
            if (arr[i][0] >= end) { // 다음 회의의 시작 시간이 현재 회의의 끝나는 시간보다 크거나 같으면
                count++; // 해당 회의를 배정합니다.
                end = arr[i][1]; // 현재 회의의 끝나는 시간을 갱신합니다.
            }
        }
        System.out.println(count); // 가능한 최대 회의 개수를 출력합니다.
    }
}

처음 한 실수 : 시작 시간대로 배열을 정렬했었고, 그렇기에 시작 시간별로 각자의 카운트값을 찾아줘 최대값을 구했다. 이러다 보니 완전 탐색을 하게돼 시간 초과

해결법 : 정렬을 회의의 끝 시간대로 정렬을 하게 되면, 순서대로 회의를 마치는 시간대로 정렬이 되어 있으니 반복문을 한 번만 돌리며 회의 가능한 시간대 별로 카운트를 해주면 그게 알아서 최대값이 된다.