[C++] 백준 13334번 : 철로

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

 

 

[풀이]

시작점과 끝점을 입력받고 끝점을 기준으로 정렬(sort)한다.

 

정렬한 값들을 루프를 돌며 검사한다. 

->  만약 도착점 - 시작점이 철로의 길이(d) 보다 길다면 우선순위 큐에 넣지 않는다.

-> 우선순위 큐 top에 있는 값과 도착점으로 부터 철로의길이(d)만큼 떨어진 곳을 비교한다.

    만약 우선순위 큐 top에 있는 값이 더 작다면 철로의 길이의 범위에 벗어나는 것이므로 pop()한다. 

-> 철로의 길이의 범위안에 있을 때까지 while문이 돌다가 maxcount값을 갱신한다. 

 

 

 

 

 

[코드]

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

priority_queue<int> q;
vector<pair<int,int>> v;
int n,d,maxcount=0;

void solve(){ 
    for(int i=0;i<v.size();i++){
        int start = v[i].first;
        int dest = v[i].second;
        
        if(dest-start>d) continue;
        q.push(-start);
        
        while(!q.empty()){
            if(-q.top()<dest-d) q.pop();
            else{
                maxcount = max(maxcount, (int)q.size());
                break;
            }
        }
    }
    cout<<maxcount;
}

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

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        if(x < y) v.push_back(make_pair(x,y));
        else v.push_back(make_pair(y,x));
    }
    cin >> d;
    
    sort(v.begin(), v.end(), compare);
    
    solve();
    
    return 0;
}