[백준] 1931 회의실 배정 (자바) : 그리디 알고리즘 [중]

✔️ 문제 설명

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

 

✔️ 문제 풀이

 

이 문제는 그리디 알고리즘 중 '활동 선택 문제(Activity Selection Problem)' 이라고 한다. 

한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제이다.

각 회의가 겹치지 않게 배정하여 할 수 있는 최대 회의 수를 구하는 문제이다. 

 

회의가 겹치지 않기 위해서는 '이전 회의의 종료 시간' 과 '이후 회의의 시작 시간'이 겹치지 않으면 된다.  

최대한 많은 활동을 선택하려면 종료 시간이 빨라야한다. 

 

서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것이다. 

 

 

종료시간이 빠른 것부터 선택하기 위해 종료시간을 기준으로 정렬을 한다. 

출처 : https://st-lab.tistory.com/145

 

겹치지 않되, 종료 시간이 빠른 회의를 선택하면 총 4개의 회의를 진행할 수 있다. 

출처 : https://st-lab.tistory.com/145

---

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

public class Main{
    static int n;
    static int[][] arr;
    static int end, total = 0;
    public static void main(String[] args)throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());

        arr = new int[n][2];

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        arrSort();
        end = arr[0][1];
        total ++;
        for(int i = 1; i<n; i++){
            if(arr[i][0] >= end){
                end = arr[i][1];
                total ++;
            }
        }
        System.out.println(total);
    }
    
    public static void arrSort(){
        Arrays.sort(arr, (arr1, arr2)->{
            if(arr1[1]==arr2[1]) return Integer.compare(arr1[0], arr2[0]); // 종료 시간이 같다면 시작 시간 오름차순으로 정렬
            else return Integer.compare(arr1[1], arr2[1]); // 종료 시간 오름차순으로 정렬
        });
    }
}

 

 

✔️ 함수 arrSort( ) 설명 :

public static void arrSort(){
    Arrays.sort(arr, (arr1, arr2) -> {
        if(arr1[1] == arr2[1]) 
            return Integer.compare(arr1[0], arr2[0]); // 종료 시간이 같다면 시작 시간 오름차순으로 정렬
        else 
            return Integer.compare(arr1[1], arr2[1]); // 종료 시간 오름차순으로 정렬
    });
}

1. Arrays.sort(arr, (arr1, arr2) -> {...}):
   
   • 람다 함수 (arr1, arr2)는 Comparator 역할을 합니다. 두 배열 arr1과 arr2를 비교하여 정렬 기준을 정의합니다.
2. 비교 기준 정의:
   • 먼저, 각 배열의 두 번째 값(즉, arr1[1], arr2[1])을 비교합니다.
     • if(arr1[1] == arr2[1]): 만약 두 배열의 두 번째 값이 같으면, 첫 번째 값(arr1[0], arr2[0])을 비교합니다.
     • Integer.compare(arr1[0], arr2[0]): 첫 번째 값들을 비교하여 정렬합니다. 이때, 오름차순 정렬을 위해 비교 결과가 음수이면 arr1이 먼저 오고, 양수이면 arr2가 먼저 오도록 합니다.
   • 그 외의 경우 (else):
     • 두 배열의 두 번째 값이 같지 않으면, 두 번째 값들을 기준으로 오름차순 정렬합니다.
     • Integer.compare(arr1[1], arr2[1]): 종료 시간을 기준으로 정렬합니다. 이때도 마찬가지로 오름차순 정렬을 수행합니다.