[java]회의실 배정 - 백준1931

문제

• 회의실 배정(백준1931)

풀이

문제 해석을 하자면,

• 대표적인 그리디 문제이다. 풀이는 너무 쉬운데 이를 증명하는게 어렵다.
• 주어진 조건을 지키며 제일 많은 회의를 할 수 있는 최대 개수를 구하라.

풀이

• 먼저 정렬 -> 회의 종료시간 기준으로 오름차순을 하고, 같다면 시작시간을 기준으로 오름차순
• cur 을 사용한 회의, inArr[i] 를 현재 탐색한 회의라고 가정했을때
  • cur.en <= inArr[i].st 를 만족하는 회의들을 찾으면 정답을 구할 수 있다.
• 왜 그런것일까? (증명)
  • 회의 종료시간 기준으로 오름차순 정렬하는 이유
    • 
    • 만약 파란색 회의를 선택했다면, 그림처럼 “파란색 네모로 색칠한 범위부분 이후(오른쪽)의 범위”(=선택 가능한 영역)에서 다음 회의를 선택할 수 있을것이다.
    • 그런데 선택 가능한 영역 중에서, 어떤 회의실을 선택해도 결과 값은 항상 1만큼 증가한다.
    • 따라서 최대 회의개수가 되려면 선택 가능한 영역 중에서 종료시간이 가장 작은 회의를 찾는건 자명하다.
  • 회의 종료시간이 같을 때 시작시간을 기준으로 오름차순 정렬하는 이유
    • 
    • 검정 -> 파랑 순으로 선택 하는게 제일 최대 회의수를 가진다.
    • 파랑 -> 검정 순으로 선택은 불가능 하다.
    • 이러한 예외 케이스 때문에 시작시간 정렬까지 고려하는 것이다.
  • 참고로 왼쪽부터 훑어가기 때문에 “종료시간” 기준으로 정렬했고, 오른쪽부터 훑어가게 된다면 “시작시간” 기준으로 정렬해도 될 것이다.

코드

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    Pair[] inArr = new Pair[N + 1];
    for (int i = 0; i < N; i++) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int st = Integer.parseInt(stk.nextToken());
        int en = Integer.parseInt(stk.nextToken());
        inArr[i] = new Pair(st, en);
    }
    //run
    Arrays.sort(inArr, 0, N);
    Pair cur = inArr[0]; //init
    int result = 1;
    for (int i = 1; i < N; i++) {
        if (cur.en <= inArr[i].st) {
            result++;
            cur = inArr[i];
        }
    }
    //output
    System.out.println(result);
}

static class Pair implements Comparable<Pair> {
    int st; int en;
    public Pair(int st, int en) {
        this.st=st; this.en=en;
    }
    @Override
    public int compareTo(Pair p) {
        if (this.en == p.en) {
            return this.st - p.st; //asc
        }
        return this.en - p.en; //asc
    }
}

느낀점

생략