백준 11000번 _ 강의실 배정

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

11000번: 강의실 배정

 접근

 주어진 시간은 1초, N의 최댓값은 20만,  S와 T는 최대10^9

 

 S, T가 INT의 범위를 넘으므로 다른 자료형을 써야한다. 나는 long long씀. 

 그리고 완전탐색으로는 풀수가 없으므로 다른 방법을 찾아야 한다. 나는 priority_queue를 이용했다.

---

 풀이방법

 첫번째 생각

 처음에는 방을 배열로 만들고 끝나는 시각을 값으로 넣어두면 아슬아슬하게 시간내에 풀지 않을까? 라는 생각을 했었다. 그런데 곰곰히 생각해보니 그저 배열로 만들게 되면 문제점이 최악의 경우에 방을 다 살펴보면 시간초과각이다.

수식 아마도?

문제점

 

 두번째 생각 

 배열을 이용해서 저 문제를 해결하려면 계산한번할때마다 sort를 해줘야해서 번거롭기도 하고 시간초과는 해결되지 못한다. 그래서 생각한것이 priority_queue를 이용해서 정렬하는 방법이다. 여기까지 생각을 했다면 나머진 별거없다.

해결책

---

 전체코드

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

#define LL long long

using namespace std;

vector<pair<LL, LL>> lessons;
int N;

bool comp(const pair<int, int>& a, const pair<int, int>& b)
{
	return a.first < b.first;
}

void Input()
{
	cin >> N;
	LL s, e;
	for (int i = 0; i < N; i++)
	{
		cin >> s >> e;
		lessons.push_back({ s, e });
	}
	sort(begin(lessons), end(lessons), comp);
}

void solve()
{
	int cnt = 0;
	priority_queue<LL, vector<LL>, greater<LL>> pri_que;
	for (auto& lesson : lessons)
	{
		LL s = lesson.first;
		LL e = lesson.second;

		//find empty room
		if (pri_que.empty())
		{
			pri_que.push(e);
			cnt++;
		}
		else
		{
			if (pri_que.top() <= s)
			{
				pri_que.pop();
				pri_que.push(e);
			}
			else
			{
				pri_que.push(e);
				cnt++;
			}
		}
	}
	cout << cnt;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);
	Input();
	solve();
	return 0;
}

---

 후기

 priority_queue의 비교함수를 작성하는 법을 알고싶다면 밑의 블로그 참고할것.

https://noel-embedded.tistory.com/329

구조체를 활용한 priority_queue 비교함수