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

백준 문제 풀이: 11000 (강의실 배정)

---

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

문제 설명:

강의 N개가 시작 시간과 종료 시간이 주어질 때, 겹치지 않게 모든 강의를 배치하려면 최소 몇 개의 강의실이 필요한지를 구하는 문제입니다. 한 강의실에서 한 번에 한 강의만 진행할 수 있고, 강의는 시작 시간과 종료 시간이 각각 주어집니다.

이 문제는 그리디 + 우선순위 큐(min-heap)를 이용한 간단하지만 중요한 스케줄링 알고리즘 문제입니다.

---

문제 해결 코드

// 강의실 배정 (우선순위 큐 이용한 스케줄링)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

pair<int, int> arr[200001];
priority_queue<int, vector<int>, greater<int>> pq;

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

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;  // 시작, 종료 시간
    }

    sort(arr, arr + n);  // 시작 시간 기준 정렬

    pq.push(arr[0].second);  // 첫 강의 종료시간 삽입
    int ans = 1;

    for (int i = 1; i < n; i++) {
        if (pq.top() <= arr[i].first) {
            // 이전 강의가 끝났다면 같은 강의실 사용 가능
            pq.pop();
        } else {
            // 새 강의실 필요
            ans++;
        }
        pq.push(arr[i].second);  // 현재 강의 종료시간 등록
    }

    cout << ans << '\n';
}

---

코드 설명

• 핵심 알고리즘: Greedy + Min-Heap (우선순위 큐)
• 구현 세부사항:
  • 강의를 시작 시간 기준으로 정렬
  • 우선순위 큐는 가장 빠르게 종료되는 강의의 종료시간을 추적
  • 현재 강의 시작 시간이 가장 짧은 종료시간보다 크거나 같다면 같은 강의실 사용 가능 → pop()
  • 그 외의 경우는 새로운 강의실이 필요하므로 ans 증가
• 시간 복잡도 분석: O(n log n), 정렬 O(n log n), 각 강의당 우선순위 큐 연산 O(log n)

---

결과

모든 강의를 겹치지 않게 배정하기 위해 필요한 최소 강의실 수를 출력합니다.

예시 입력:

3
1 3
2 4
3 5

예시 출력:

2

우선순위 큐를 활용한 효율적인 스케줄링 문제로, 면접에서도 자주 등장하는 유형입니다. 다른 최적화 방법이 있다면 댓글로 공유해 주세요!