[백준] 1931 회의실 배정(Sliver.1) - 그리디(활동 선택 문제(Activity Selection Problem))

문제

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

코드

이 문제는 그리디(Greedy) 알고리즘의 활동 선택 문제(Activity Selection Problem)이다.

활동 선택 문제(Activity Selection Problem)란 시작 시간과 종료 시간이 주어진 여러 활동 중 시간이 겹치지 않으면서 가장 많은 활동을 할 수 있는 집합을 고르는 문제이다.

 

문제를 푸는 방법은 다음 두 가지를 고려하면 된다.

1. 이전 활동의 종료 시간과 다음 활동의 시작 시간이 겹치면 안된다.
2. 최대한 많은 활동을 선택하기 위해서 종료 시간이 가능한 빨라야한다.

위 두 가지 조건을 충족하기 위해서 종료 시간을 기준으로 오름차순 정렬을 한 후 그리디(Greedy)를 이용하여 이전 활동 종료 시간과 다음 활동 시작 시간이 겹치지 않는 활동을 뽑으면 된다.
아래와 같이 (1,4), 5,7), (8,11), (12,14) 활동이 선택된다.

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

public class _1931 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] meeting = new int[n][2];
        // 시간 복잡도: O(n)
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meeting[i][0] = start;
            meeting[i][1] = end;
        }

//        Arrays.sort(meeting, (o1, o2) -> {
//            return o1[1]-o2[1];
//        });
        /**
         * o1[1](앞) < o2[1](뒤): (o1, o2) 작은 숫자가 앞으로(순서 유지)
         * o1[1](앞) > o2[1](뒤): (o2, o1) 작은 숫자가 뒤로(순서 변경)
         * o1[1](앞) == o2[1](뒤): (o1, o2) 순서 유지
         */
        Arrays.sort(meeting, (o1, o2) -> {
            if (o1[1] == o2[1]) {
                return Integer.compare(o1[0], o2[0]);
            }
            return Integer.compare(o1[1], o2[1]);
        });

        int cnt = 0;
        int now = 0;
        for (int i = 1; i < n; i++) {
            if (now <= meeting[i][0]) {
                now = meeting[i][1];
                cnt++;
            }
        }

        System.out.println(cnt);

    }
}