22.03.18 - [BOJ] 1931. 회의실배정

[suhyunsim]

문제

• 회의실 배정

핵심 아이디어

• task scheduling problem

가능한 풀이

1. O(2^n): 모든 가능한 배정 방법을 확인
2. DP풀이 -> O(n^2): 회의를 끝나는 시간이 빠른 순으로, 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬
   • D[i] = i번째 회의를 마지막으로 진행했을 때 최대 회의의 수
   • D[i] = max(D[j]) + 1 (j번째 회의의 끝나는 시간이 i번째 회의의 시작 시간 이하인 모든 j)
3. 그리디 풀이
   • 명제: 현재 시간이 t라고 할 때 시작 시간이 t이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해 (귀류법으로 증명 가능)

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q1931;

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] meetings = new int[n][2];
        for (int i = 0; i < n; i++) {
            meetings[i][0] = sc.nextInt();
            meetings[i][1] = sc.nextInt();
        }
        Arrays.sort(meetings, (o1, o2) -> {
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });
        int answer = 0;
        int now = 0;
        for (int i = 0; i < n; i++) {
            if (now <= meetings[i][0]) {
                now = meetings[i][1];
                answer++;
            }
        }
        System.out.println(answer);
    }
}