회의실 배정 - Greedy

무식하게 풀 수 없을까? 모든 회의의 선택을 고려하려면 각 회의를 선택할 것인지 말 것인지 결정하면 된다. 따라서 2ⁿ의 경우의 수가 생기므로 시간 초과가 발생한다. 

 

그럼 가장 많은 회의를 할 수 있도록 각 회의를 탐욕적으로 선택할 수 없을까? → 가장 빨리 끝나는 회의만을 선택한다. 가장 빨리 끝나는 회의만을 선택해도 문제의 답을 구할 수 있게 된다.

 

백준 1931번 회의실 배정 문제이다.

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        Pair[] arr = new Pair[N];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start_time = Integer.parseInt(st.nextToken());
            int end_time = Integer.parseInt(st.nextToken());
            arr[i] = new Pair(start_time, end_time);
        }

        Arrays.sort(arr,(Pair a, Pair b)-> {
            if(a.end_time == b.end_time) return a.start_time - b.start_time;
            return a.end_time - b.end_time;
        });

        int answer = 1;
        Pair select = arr[0];
        for(int i=1; i<N; i++) {
            if(select.end_time <= arr[i].start_time) {
                answer++;
                select = arr[i];
            }
        }
        System.out.print(answer);
    }
}

class Pair {
    int start_time;
    int end_time;
    Pair(int start_time, int end_time) {
        this.start_time = start_time;
        this.end_time = end_time;
    }
}