[BOJ] 1931번. 회의실 배정 - Greedy 알고리즘

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

1931번: 회의실 배정

Greedy 알고리즘의 가장 기본 문제로 많이 나온다.

 

탐욕법은 미래는 생각하지 않고 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.

따라서 이 문제에서 길이와 상관없이 가장 먼저 끝나는 회의부터 선택하고, 겹치는 회의를 모두 제거한 뒤 모든 회의들이 없어질때까지 반복하면 최적해가 구해질 것이다.

하지만 이렇게는 전체 시간 복잡도가 O(N^2)이 되므로,

먼저 회의시간을 빨리 끝나는 순서대로 sort 하면, 겹치는 회의를 없앨 필요없이 순회하면서 선택하기만 하면 된다.

이렇게하면 정렬에 걸리는 시간 O(NlogN) 이 시간복잡도가 된다.

 

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
    public static int N;
    public static int[][]arr;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N][2];
        for(int i=0; i<N; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
 
        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2){
                if(o1[1] == o2[1]){
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });
 
        int count = 0;
        int prev_end_time = 0;
        for(int i=0; i<N; i++){
            if(prev_end_time <= arr[i][0]){
                prev_end_time = arr[i][1];
                count++;
            }
        }
 
        System.out.println(count);
 
        sc.close();
    }
}