백준 1374번 강의실 - C++

문제

---

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

 

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

 

문제 링크

https://www.acmicpc.net/problem/1374

 

풀이

---

우선 순위 큐를 이용해 그리디하게 접근하면 되는 문제다.

 

예제를 보면서 흐름을 따라가보자.

아래와 같이 데이터가 들어온다고 해보자. (강의 번호는 의미없는 데이터이기에 제거했다.) ▼

 

우선 이를 시작 시간을 기준으로 정렬한다. ▼

 

그리고 하나씩 배정을 해보는 것을 시작하는데, 가장 빨리 끝나는 시간을 늘 갱신시켜줘야 한다.

우선은 처음 들어온 값이니 강의실 수를 하나 늘려주고 가장 빨리 끝나는 시간은 14로 해준다. ▼

 

그 다음으로 들어온 시간은 3 - 8 인데, 3이 14보다 먼저 시작하므로 강의실을 하나 늘려준다.

그러나 끝나는 시간이 8로, 14보다 작기에 가장 빨리 끝나는 시간을 8로 갱신해준다. ▼

 

"갱신은 어떻게 해주는데?"

 

해당 시점의 갱신은 우선 순위 큐가 알아서 해준다.

그러니 일단 값만 넣으면 알아서 갱신이 된다.

 

다음으로 들어온 값은 6 - 20.

가장 빨리 끝나는 시간인 8보다 6이 작으므로, 강의실을 하나 늘려준다. ▼

 

다음으로 들어온 시간은 6 - 27.

이 역시도 8보다 작기에 강의실을 하나 늘려준다. ▼

 

다음으로 들어온 시간은 7 - 13.

이 역시도 8보다 작기에 강의실을 하나 늘려준다. ▼

 

이 다음으로 들어오는 시간은 12 - 18.

8보다 크기에 강의실이 겹치지 않는다.

그렇기에 강의실을 늘리지 않고, 가장 빨리 끝나는 시간을 8에서 13으로 갱신해준다. ▼

 

"이 갱신도 자동으로 되는건가?"

 

이 갱신은 8을 우선 순위 큐에서 `pop()`을 해야 실행된다.

이렇게 강의실이 늘어나지 않는다면 큐의 가장 앞을 `pop()`하여 갱신해준다.

 

그 다음은 그 과정의 반복이 된다.

 

이런 흐름으로 진행하면 강의실이 얼마나 필요한 지 알 수 있다.

 

 

C++ 코드

---

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int N, answer;
pair<int ,int> R[100001];
priority_queue<int, vector<int>, greater<int>> PQ;

void input() {
  int tmp;

  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> tmp >> R[i].first >> R[i].second;
  }
}

void solve() {
  sort(R, R + N);
  
  for (int i = 0; i < N; i++) {
    if (PQ.size()) {
      if (PQ.top() > R[i].first) {
        answer++;
      } else {
        PQ.pop();
      }
    } else {
      answer++;
    }
    PQ.push(R[i].second);
  }
}

void output() {
  cout << answer;
}

int main() {
  input();
  solve();
  output();
}