백준 11000 강의실배정 (C++)

그리디, 우선순위 큐

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

11000번: 강의실 배정

시간 범위로 입력이 들어오고 특정 시간이 그 범위에 껴있는 갯수가 최대인 값을 찾는다.

시작시간 순으로 정렬해서 보면서 시작했는데 끝나지 않은 수업의 갯수가 사용중인 강의실의 수.

강의 시간을 시작시간 순으로 정렬하고

이미 시작한 수업은 끝나는 시간을 기준으로 우선순위 큐에 넣는다.

끝날 시간이 되면 큐에서 빼고 시작한후면 뺀다.

큐의 크기가 필요한 강의실의 크기.

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int mymax = -1;
struct times {
	int start;
	int end;
};
struct cmp {
	bool operator() (const times& a, const times& b) {
			return a.start < b.start;
	}
};
struct cmptwo {
	bool operator() (const times& a, const times& b) {
		return a.end >  b.end;
	}
};
priority_queue <times, vector<times>, cmptwo> q;
times arr[200000];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	int inputnum;
	cin >> inputnum;
	for (int i = 0; i < inputnum; i++)
	{
		cin >> arr[i].start >> arr[i].end;
	}
	sort(arr, arr + inputnum, cmp());
	for (int i = 0; i < inputnum; i++)
	{
		if (!q.empty())
		{
			while (q.top().end <= arr[i].start) {
				q.pop();
				mymax = max(int(q.size()), mymax);
			}
		}

		q.push(arr[i]);
		mymax = max(int(q.size()), mymax);
	}

	cout << mymax;
}