백준 1931번 [회의실 배정](C++) -yes6686- 티스토리

백준 문제 풀이: 1931 [회의실 배정]

---

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

문제 설명:

한 개의 회의실이 있을 때, 회의가 겹치지 않도록 최대한 많은 회의를 배정하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 회의의 수 `n`이 주어집니다. (1 ≤ n ≤ 100,000)
• 다음 `n`개의 줄에는 각 회의의 시작 시간과 끝나는 시간이 공백으로 구분되어 주어집니다.
• 각 회의의 시작 시간과 끝나는 시간은 2³¹-1 이하의 자연수입니다.

출력 조건:

• 첫째 줄에 회의실에서 열 수 있는 최대 회의 수를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int, int>> v;

    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        v.push_back({end, start}); // 끝나는 시간을 기준으로 정렬하기 위해 저장
    }

    sort(v.begin(), v.end()); // 끝나는 시간 오름차순으로 정렬

    int count = 1; // 첫 번째 회의 선택
    int lastEnd = v[0].first;

    for (int i = 1; i < v.size(); i++) {
        if (v[i].second >= lastEnd) { // 다음 회의가 현재 회의 끝난 이후에 시작한다면 선택
            count++;
            lastEnd = v[i].first;
        }
    }

    cout << count << '\n';
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 그리디 알고리즘을 사용하여 회의실에 최대한 많은 회의를 배정합니다.

• 입력 처리:
  • 회의의 시작 시간과 끝나는 시간을 입력받아 `vector`에 저장합니다.
  • 끝나는 시간을 기준으로 정렬하기 위해 `pair`의 첫 번째 요소에 끝나는 시간을 저장합니다.
• 정렬:
  • `sort`를 사용하여 끝나는 시간을 기준으로 오름차순 정렬합니다.
• 그리디 선택:
  • 가장 먼저 끝나는 회의를 선택합니다.
  • 현재 회의의 끝나는 시간 이후에 시작하는 회의만 선택합니다.

시간 복잡도 분석:

• 정렬: O(n log n).
• 회의 선택: O(n).

전체 시간 복잡도는 O(n log n)으로 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5
1 4
2 3
3 5
5 7
6 8

출력:
3

회의실을 최대한 배정하여 총 3개의 회의를 열 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!