11000번: 강의실 배정

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

11000번: 강의실 배정

1. 문제 분석 s, t의 범위가 10^9까지이기 때문에 무식하게 배열을 채우는 방법은 안된다. 그렇기 때문에 최대 범위가 200000인 N에 집중해야 하는데 (N/2)^2도 1초가 넘기 때문에 새로운 무언가가 필요했다.

2. 코드 작성

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

pair<int, int> p_list[200000];
int clas[200000];


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

priority_queue<int, vector<int>, greater<int>>	pq;

int main()
{
	int N, cnt = 0;

	cin >> N;
	for (int i = 0;i < N;i++) {
		cin >> p_list[i].first >> p_list[i].second;
	}
	sort(p_list, p_list + N, comp);
	pq.push(p_list[0].second);
	for (int i = 1;i < N;i++)
	{
		if (pq.top() > p_list[i].first) pq.push(p_list[i].second);
		else {
			pq.pop();
			pq.push(p_list[i].second);
		}
	}
	cout << pq.size();
	return 0;
}

3. 키워드

#우선순위큐

4. 설명

#include <queue> //priority_queue
#include <functional> //less, greater
// top,pop=min heap
priority_queue<int, vector<int>, greater<int>>	pq;
// top,pop=max heap
priority_queue<int, vector<int>, less<int>>	pq;