[BaekJoon] 1931번 - 회의실 배정 [Java][C++]

문제 링크

---

1. 문제 풀이

전형적인 그리디 알고리즘의 활동 선택 문제로 한 개의 회의실에서 최대한 많은 회의를 하려면 회의 시간이 빨리 끝나는 회의부터 회의실에 배정하면 된다. 따라서 회의의 종료 시간을 기준으로 오름차순으로 정렬한 후 해당 회의를 배정하면 다음 회의는 이전에 배정한 회의의 종료 시간보다 시작 시간이 같거나 늦는 경우 배정하는 과정을 반복하면 된다. 이때 회의가 시작과 동시에 종료하는 경우도 있어서 종료 시간이 동일하면 일찍 시작하는 회의가 앞에 오도록 정렬을 해줘야 한다.

예를 들어 $1$ ~ $3$ 동안 진행하는 회의와 $3$ ~ $3$ 동안 진행하는 회의가 있는 경우 $1$ ~ $3$ 동안 진행하는 회의가 앞에 오도록 정렬하면 $1$ ~ $3$ 동안 진행하는 회의 이후 $3$ ~ $3$ 동안 진행하는 회의를 할 수 있지만, $3$ ~ $3$ 동안 진행하는 회의가 앞에 오도록 정렬하면 $3$ ~ $3$ 동안 진행하는 회의 이후 $1$ ~ $3$ 동안 진행하는 회의는 할 수 없다.

---

2. 코드

1. 풀이 [Java]

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));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[][] map = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(map, (o1, o2) -> {
            if (o1[1] != o2[1]) return Integer.compare(o1[1], o2[1]);
            return Integer.compare(o1[0], o2[0]);
        });

        int end = 0;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (map[i][0] < end) continue;

            end = map[i][1];
            cnt++;
        }

        System.out.println(cnt);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> v(n);
    for (auto& p : v) cin >> p.second >> p.first;
    sort(v.begin(), v.end());

    int end = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (v[i].second < end) continue;

        end = v[i].first;
        cnt++;
    }

    cout << cnt;
}

---