[백준 / 실버1] 1931번 회의실 배정 (Java)

문제 보기

풀이

• O(nlog n) 만큼의 정렬(사실 Arrays.sort()는 최악 O(n^2)이긴 함) + O(n) 만큼의 순회로 문제를 해결하기 위해 그리디로 접근
  
  
• 2차원 int 배열 usages에 {startTime, endTime}인 int 배열을 입력 받음
• 최대한 많은 예약을 하기 위해선 endTime이 빠른 것부터 예약시키면 됨 -> 그리디
• usages를 endTime 기준으로 오름차순 정렬해 줌, 만약 endTime이 같으면 startTime 기준으로 정렬
• for문을 돌면서 새로운 usage의 시작 시간이 endTime보다 크거나 같으면 answer++ 하고 endTime 갱신
• endTime이 같은 경우 startTime 기준으로 정렬시킨 이유는 {{1, 1}, {0, 1}}과 같이 시작하자마자 끝나는 경우가 존재하기 때문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[][] usages = new int[num][2];
        for (int i = 0; i < num; i++) {
            usages[i] = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        }

        Arrays.sort(usages, (o1, o2) -> o1[1] != o2[1] ? o1[1] - o2[1] : o1[0] - o2[0]);

        int answer = 0;
        int endTime = 0;
        for (int i = 0; i < usages.length; i++) {
            if (usages[i][0] >= endTime) {
                answer++;
                endTime = usages[i][1];
            }
        }

        System.out.println(answer);
    }
}