회의실 배정(Greedy)

한 개의 회의실을 사용하고자 하는 n개의 회의가 있을 때, 각 회의의 시작 시간과 끝나는 시간이 주어진다. 이때, 회의가 겹치지 않게 하면서 회의실을 최대한 많이 사용할 수 있도록 배정해야 한다. 단, 한 회의가 끝나는 동시에 다른 회의가 바로 시작될 수 있으며, 중간에 중단될 수 없다.

 

문제 해결 아이디어

이 문제는 그리디 알고리즘으로 해결할 수 있다. 끝나는 시간이 가장 빠른 회의를 먼저 선택하는 것이 최적의 해를 보장하는 방법이다. 이렇게 해야, 다음 회의가 겹치지 않게 최대한 많이 배정할 수 있다.

1. 정렬 기준

• 회의의 끝나는 시간을 기준으로 오름차순 정렬한다.
• 끝나는 시간이 같다면 시작 시간을 기준으로 오름차순 정렬한다.

2. 그리디 선택

• 첫 번째 회의를 선택한 후, 선택된 회의의 끝나는 시간 이후에 시작하는 회의를 선택한다.

문제 풀이 과정

1. 회의 정보를 정렬

• 먼저 주어진 회의를 끝나는 시간을 기준으로 오름차순 정렬한다. 끝나는 시간이 같을 경우 시작 시간을 기준으로 오름차순 정렬한다.

2. 회의 선택

• 가장 빨리 끝나는 회의를 선택하고, 그 회의의 끝나는 시간 이후에 시작하는 회의를 선택하는 방식으로 최대 회의 수를 찾는다.

입력 설명

• 첫 번째 줄에 회의의 수 n이 주어진다. (1 ≤ n ≤ 100,000)
• 두 번째 줄부터 n개의 회의의 시작 시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 0시부터 시작한다.

출력 설명

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

입력 예시 1

5
1 4
2 3
3 5
4 6
5 7

 

출력 예시1

3

예시 설명: (2, 3), (3, 5), (5, 7) 회의가 선택된다.

 

코드 

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 회의의 시작 시간(ft)과 끝나는 시간(et)을 나타내는 클래스
class Metting {
    int ft, et;

    // 생성자: 각 회의의 시작 시간과 끝나는 시간을 초기화
    public Metting(int ft, int et) {
        this.ft = ft;
        this.et = et;
    }
}

class Main {

    // 최대 사용할 수 있는 회의 수를 구하는 메서드
    public static int solution(ArrayList<Metting> arr) {
        int cnt = 0;  // 선택된 회의 수를 저장할 변수

        // 회의를 끝나는 시간 기준으로 오름차순 정렬
        // 끝나는 시간이 같으면 시작 시간 기준으로 오름차순 정렬
        arr.sort((a, b) -> {
            if (a.et == b.et) return a.ft - b.ft;  // 끝나는 시간이 같으면 시작 시간을 비교
            return a.et - b.et;  // 끝나는 시간 기준으로 오름차순 정렬
        });

        int et = 0;  // 마지막으로 선택된 회의의 끝나는 시간을 저장할 변수

        // 정렬된 회의를 하나씩 확인
        for (Metting ob : arr) {
            // 현재 회의의 시작 시간이 마지막 회의의 끝나는 시간보다 크거나 같다면 선택 가능
            if (ob.ft >= et) {
                cnt++;  // 선택된 회의 수 증가
                et = ob.et;  // 현재 회의의 끝나는 시간을 마지막 회의 끝나는 시간으로 업데이트
            }
        }

        return cnt;  // 선택된 회의 수 반환
    }

    // 프로그램의 시작점
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  // 입력을 받기 위한 BufferedReader
        int n = Integer.parseInt(br.readLine());  // 회의의 수 입력

        // 회의 정보를 저장할 ArrayList
        ArrayList<Metting> metting = new ArrayList<>();

        // 각 회의의 시작 시간과 끝나는 시간을 입력받아 리스트에 추가
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());  // 한 줄의 입력을 공백으로 구분
            metting.add(new Metting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));  // 입력된 값을 회의 객체로 생성하여 리스트에 추가
        }

        // 최대 사용할 수 있는 회의 수를 출력
        System.out.println(solution(metting));
    }
}

• 입력 처리: BufferedReader로 입력을 받아 Metting 객체 리스트에 저장한다. 각 회의의 시작 시간(ft)과 끝나는 시간(et)을 입력받는다.
• 정렬: 회의를 끝나는 시간 기준으로 오름차순 정렬하고, 끝나는 시간이 같을 경우 시작 시간 기준으로 오름차순 정렬한다.
• 회의 선택: 마지막으로 선택된 회의의 끝나는 시간을 기준으로, 이후 시작되는 회의만 선택하여 카운트를 증가시킨다.

시간 복잡도

• 정렬: O(n log n) 시간 복잡도.
• 회의 선택: 정렬된 리스트를 순회하며 선택하는데 O(n)이므로, 전체 시간 복잡도는 **O(n log n)**이다.

결론

이 알고리즘은 그리디 알고리즘을 사용해 끝나는 시간이 빠른 회의를 먼저 선택하여, 최대한 많은 회의를 선택할 수 있는 최적의 해를 구한다.