[백준/BOJ] 1689. 겹치는 선분 [Gold 4]

1689. 겹치는 선분

문제출처 : https://www.acmicpc.net/problem/1689

code

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

int main()
{
	ios_base::sync_with_stdio(false);

	int N, x, y, cnt = 1;
	vector<pair<int, int>> arr;
	priority_queue<int> q;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x >> y;
		arr.push_back({ x,y });
	}

	sort(arr.begin(), arr.end());

	q.push(-arr[0].second);
	for (int i = 1; i < N; i++)
	{
		while (!q.empty() && -q.top() <= arr[i].first)
		{
			q.pop();
		}
		q.push(-arr[i].second);
		cnt = max(cnt, (int)q.size());
	}

	cout << cnt;

	return 0;
}

이거 푸느라 새벽을 꼬박 세웠다.
요즘 골드문제가 어려워서 잘 못풀고있었는데, 오늘만큼은 무조건 푼다는 각오로 풀었다.
6시간동안 뒤적이다가
우선순위 큐라는 자료구조를 이용하면 엄청 쉽다는것을 깨달았다.
물론 이건 온전한 내코드는 아니지만ㅠㅠ
중간에 푸쉬할때 음수는 왜넣나 1시간동안 구글링했는데,
일반 큐랑 다르게 우선순위 큐는 가장 큰값을 top으로 두는데, 이때 음수로 두면 절대값이 가장 작은 값이 top으로 오게 할 수 있었다.

이번에 개고생했으니 다음에는 더 잘 풀 수 있을것 같다.