[BOJ] 11000 강의실 배정

입력된 일정들을 겹치지 않게 구성하기 위해 필요한 강의실의 최솟값을 구하는 문제이다.

처음엔 queue로 풀고, 구성하지 못한 경우 뒤로 넘기는 방식을 선택했는데

이렇게 하니 worst case에서 시간복잡도가 O(n^2)가 되어 버린다.

 

생성된 방들의 일정 중 가장 나중에 끝나는 일정의 시간만 저장하고, 그것들을 비교하면 되는데,

방의 갯수가 늘어나게 될 때 모든 방을 불필요하게 비교하지 않아도

Priority queue로 구성하게 되면, 가장 일찍 끝나는 방의 경우만 살피면 되기 때문에 시간 복잡도를 n에서 logn으로 줄일 수 있게 된다. 

고로 priority-queue엔 가장 늦게 끝나는 스케줄의 끝나는 시간만 넣어놓으면 된다. 

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
 
int A, B, C, N, d1, d2, res, length;
int lecture_start, lecture_end;
 
using namespace std;
 
vector<pair<int, int>> allPair;
priority_queue<int, vector<int>, greater<int>> pq;
 
int main(){ 
  scanf("%d", &N);
 
  for(int i = 0; i < N; i++){
    scanf("%d %d", &d1, &d2);
    allPair.emplace_back(make_pair(d1, d2));
  }
 
  sort(allPair.begin(), allPair.end());
 
  pq.push(allPair[0].second); // 첫번째가 끝나는 마지막꺼
 
  for(int i = 1 ; i < N ; i++){
    lecture_start = allPair[i].first;
    lecture_end = allPair[i].second;
 
    if(pq.top() > lecture_start){
      // 시간대가 겹치면
      pq.push(lecture_end); // lecture가 더 필요하니 넣어라.
    }
    else { // 안겹치면
      pq.pop(); // 지금있는거 빼고 
      pq.push(lecture_end); // 새로운 end를 넣어라.
    }
  }
 
  printf("%d", pq.size());
  return 0;
}