개요

[링크]백준 11000: 강의실 배정

백준 1931과 비슷한 문제인데,
이 문제에선 최대한 많은 강의를 들을 수 있느냐가 아니라
모든 강의를 들으려 할때 최소한의 강의실 수를 구해야한다.

접근 방식

• 첫번째 방식
  pair<int,int>를 이용해서 값을 얻어오는 데,
  algorithm헤더의 sort를 이용해 입력값 pair을 정렬하면
  알아서 시작시간과 종료시간이 정렬이 되니,
  시작시간과 종료시간 차이가 적은 값들을 쭈욱 고르고
  해당 pair을 방문했다라는 의미로 vector< int > used에
  체크를 해서, 한번 조사한 pair는 다시 조사 안하도록
  구현을 했다.

void solution() {																	//답 도출함수
	sort(v.begin(), v.end());														//정렬
	int currentfirst = 0, currentsecond = 0, ans = 0;								//지금 v.first값,v.second값,강의실 수
	for (int i = 0; i < v.size(); i++) {
		if (used[i] > 0) continue;													//s와 t가 같은 값은 안들어오니 한번 들으면 들은 시간대는 체크
		used[i] ++;
		ans++;
		currentsecond = v[i].second;												//각 i값에서 반복 (혹시 맨처음값부터 시작한게 답이 아닐수도 있으므로) 

		for (int j = i+1; j < v.size(); j++) {

			if (used[j] > 0) continue;

																					//first값이 새로운 값으로 넘어왓다는 뜻이므로
			if (v[j].first < currentsecond)	continue;								//currentsecond값나올때까지 스킵
				
			used[j]++;
			currentsecond = v[j].second;											//이제 v[j].first가 currentsecond값보다 같거나 크므로
		}
	
	}
	cout << ans;

어찌되었든 N이 20만이 들어오면 시간초과가 난다.

• 두번째 방식
  검색의 힘을 빌린 결과, 대다수의 풀이법이
  우선순위 큐를 사용하여 쉽게 구현했다.
  우선순위 큐는 종료시간이 빠른순으로 넣어지게 되고,
  큐 안에서 종료시간이 큰게 top으로 오게된다.

  만약 시작시간이 우선순위 큐의 top보다 크면
  종료시간보다 더 큰값이므로
  우선순위큐에서 종료시간이 제일 작은 값을 pop하고 해당 시작시간을 넣는다.

  만약 시작시간이 우선순위 큐의 top보다 작다면
  새로운 강의실이 필요하므로 우선순위 큐에 넣어준다.

  마지막에 우선순위 큐의 원소 갯수가 총 강의실 갯수다.

코드

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

vector<pair<int,int>> v;
priority_queue<int,vector<int>,greater<int>> pq;	//내림차순으로 정렬하는 우선순위 큐(작은게 더앞으로)

 void input() {										//입력값 받은후 벡터와 우선순위큐에 넣어줌
	 int sTime = 0, eTime = 0, amount = 0;
	 cin >> amount;
	 for (int i = 0; i < amount; i++) {
		 cin >> sTime >> eTime;
		 v.push_back(make_pair(sTime, eTime));
	 }
	 sort(v.begin(), v.end());
	 pq.push(v[0].second);
 }
 void solution() {									//우선순위 큐를 이용한 풀이
	 for (int i = 1; i < v.size(); i++) {
		 if (v[i].first >= pq.top()) {
			 pq.pop();
			 pq.push(v[i].second);
		 }
		 else
			 pq.push(v[i].second);
	 }

	 cout << pq.size();
 }

int main() {
	input();
	solution();
}

문풀후생

우선순위 큐에 넣고 제일 작은값만 비교하면 되는
방법이 참 기발한것 같다.