[C++] BOJ 11000 강의실 배정

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

문제 핵심

• 시간 제한은 1초 / 1 ≤ N ≤ 200,000 / 0 ≤ Si < Ti ≤ 10^9
• 모든 수업을 가능하게 하는 강의실 개수의 최소값 구하기

문제 풀이 과정

*시간 제한은 1초이므로 연산 횟수는 10^8 안에 끝내야함.

1. 늦게 끝나는 순서대로 강의를 정렬한다.
2. 들어갈 수 있는 강의실이 있는지 확인한다.
   1. 없는 경우 새로운 강의실을 마련한다.
   2. 있는 경우 (뒤)시작 시간과 (앞)종료 시간이 가장 가까운 곳에 입력한다.

탐색하는 과정에서 2중 for문이 사용될 경우 시간 초과가 발생하므로 우선순위 큐를 이용해서 비교 과정에 드는 연산을 줄이도록 한다.

문제 코드

// BOJ 11000 강의실배정
// 시간복잡도 O(NlogN)
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct Schedule {
  int start, end;
  Schedule(int s, int t) : start(s), end(t) {} // 생성자 
};

// 끝나는 시간 기준 내림차순 정렬 // 늦게 끝나는 걸 앞으로
struct cmp1 {
  bool operator()(Schedule a, Schedule b){
    return a.end < b.end;
  }
};

// 시작하는 시간 기준 내림차순 정렬 // 늦게 시작하는 걸 앞으로
struct cmp2 {
  bool operator()(Schedule a, Schedule b){
    return a.start < b.start;
  }
};

priority_queue<Schedule, vector<Schedule>, cmp1> timeTable;
priority_queue<Schedule, vector<Schedule>, cmp2> room;

int main() {
  // 1. 입력 받기
  int N, answer=0;
  
  cin >> N;
  for(int i=0;i<N;i++){
    int s, t;
    cin >> s >> t;
    timeTable.push(Schedule(s,t));
  }

  // 2. 들어갈 수 있는 강의실 존재 여부 탐색
  // 시간 제한이 1초이므로 시간복잡도가 O(N)이 넘어가면 안됨.
  
  while(!timeTable.empty()){
    Schedule sch = timeTable.top();
    timeTable.pop();
		
    // 처음이라 들어갈 수 있는 강의실이 없다 -> 새로운 강의실
    if(room.empty()){
      room.push(Schedule(sch.start, sch.end));
      continue;
    }

    Schedule rsv = room.top();
    room.pop();
		// 들어갈 수 있는 강의실이 있다 -> (뒤)시작 시간과 (앞)종료 시간이 가장 가까운 곳으로
    if(rsv.start >=sch.end){
			// 강의실의 시작 시간과 종료 시간 갱신하여 다시 추가
      room.push(Schedule(sch.start, rsv.end)); 
      continue;
    }
		// 들어갈 수 있는 강의실이 없다 -> 새로운 강의실
    else {
      room.push(Schedule(rsv.start, rsv.end));
      room.push(Schedule(sch.start, sch.end));
    }
  }
  answer = room.size();
  cout<<answer;
}

새롭게 알게된 점

우선순위 큐

https://kbj96.tistory.com/15
https://kibbomi.tistory.com/149

• 우선순위 큐는 반복자, 인덱스를 이용한 접근이 불가능하다.
  • 값을 확인하려면 순회하면서 top(), pop()을 반복하면서 다 뽑아내는 수 밖에 없다.
• 우선순위 큐의 삽입과 삭제는 O(logN)이므로 우선순위 큐를 이용한 정렬은// O(NlogN)

틀린 부분이 있다면 지적해주세요. 읽어주셔서 감사합니다!