[백준] 1931 회의실 배정 쉬운 풀이 ^^

1. 문제 설명 📌

문제 링크

회의시간의 시작과 끝이 주어질 때, 최대한 많은 강의를 회의실에 배정해라 (A 강의의 끝시간과 B 강의의 시작 시간이 같으면 연달아 배정할 수 있는 것으로 간주한다.)

2. 접근 방식 🗃️

KEY WORDS: GREEDY ALGORITHM
Greedy Algorithm은 선택의 순간에 최적의 선택지를 고르는 것이 전체 문제에서 최적의 선택을 하는 것이라 가정하는 알고리즘이다.

1. 빨리 끝나는 순으로 회의를 정렬

2. 제일 빨리 끝나는 회의가 A라면 A 회의 이후에 시작할 수 있으면서도, 최대한 빨리 끝나는 회의를 선택하는 것이 전체 문제에서 봤을 때 최대한 많은 강의를 고를 수 있는 방법임.

3. 2번을 모든 회의를 돌아보며 더 이상 고를 수 있는 회의가 없을 때까지 반복

3. 코드 소개 🔎

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

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

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            lecture[i][0] = Integer.parseInt(st.nextToken());
            lecture[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(lecture, (a,b) -> {
            if(a[1] == b[1]) return a[0] - b[0];
            return Integer.compare(a[1], b[1]);
        });

        int end_time = lecture[0][1];
        int cnt = 1;
        for(int i = 1; i < N; i++){
            if(lecture[i][0] < end_time) continue;

            cnt++;
            end_time = lecture[i][1];

        }
        System.out.println(cnt);
    }
}

4. 배운 것들 🎯

회의를 그저 빨리 끝나는 순으로 정렬했을 때는 안 풀리는 반례가 존재한다. 다음을 보자

"회의 개수": 2

4 4
1 4

다음과 같이 회의가 1시간 안에 끝나는 경우이다. 이와 같이 종료 시간이 같을 경우 시작 시간이 빠른 순으로 정렬하지 않으면, 회의를 더 많이 진행할 수 있는 기회를 놓친다.

이것 때문에 처음에 틀렸다 😂