백준 20440

문제링크

https://www.acmicpc.net/submit/20440/28843659

문제

풀이

1. 벡터에 시작시간과 끝시간을 모두 push 한 후 시작시간을 기준으로 오름차순으로 정렬한다.
2. 끝나는 시간을 기준으로 먼저 끝나는것이 높은 우선순위를 가지도록 우선순위 큐를 선언한다.
3. 벡터원소의 시작시간이 top() 원소의 끝나는 시간보다 작아질때까지 pop() 을 실행하고 그 뒤에 벡터원소를 push한다.
4. pq.size() 와 ans_size를 비교한다.
   4-1) ans_size가 pq.size()보다 크다면 ans_size 와 ans_range를 갱신
   4-2) ans_size가 pq.size()와 같다면 ans_range와 벡터 원소의 구간이 이어지는 경우 ans_range를 갱신해준다.

시행착오

오름차순 정렬 후 우선순위큐에 push하는 것까지 금방 접근했는데 그 뒤에 막혀서 한참 고민했다.

코드

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	vector<pair<int, int>> vec;
	pair<int, int> ans_range = { 0,0 };
	int ans_size = 0;

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int ent, ext;
		cin >> ent >> ext;
		vec.push_back({ ent,ext });
	}
	sort(vec.begin(), vec.end());

	priority_queue<pair<int, int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;
	for (int i = 0; i < vec.size(); i++) {
		while (!pq.empty() && pq.top().first <= vec[i].first) pq.pop();
		pq.push({vec[i].second, vec[i].first});

		if (pq.size() == ans_size && ans_range.second == vec[i].first) {
			ans_range.second = pq.top().first;
		}
		else if (pq.size() > ans_size) {
			ans_size = pq.size();
			ans_range = { vec[i].first,pq.top().first };
		}
	}

	cout << ans_size << '\n' << ans_range.first << ' ' << ans_range.second;

}

후기

분명 어디선가 풀어봤던 문제다.
요즘 알고리즘에 소홀했더니 이 문제도 고전했다.
열심히 하자.