[백준]철로(13334)

문제 링크 : [백준]철로(13334)

13334번: 철로

문제 설명

N명의 사람이 사는 집의 위치와 사무실의 위치가 주어집니다.(위치는 모두 일직선 위에 존재)

길이 d의 연속된 철로를 설치하여, 최대한 많은 사람의 사무실과 집을 포함하도록 할 때, 몇명까지 포함되게 만들 수 있는지 구하세요.

입력

N(사람의 수, 1 <= N <= 100,000)

H_i O_i(집의 위치, 사무실의 위치, -100,000,000 <= H_i, O_i <= 100,000,000)

D(철로의 길이, 1 <= D <= 200,000,000)

8
5 40
35 25
10 20
10 25
30 50
50 60
30 25
80 100
30

 

출력

4

 

카테고리

#정렬 #우선순위큐

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. 먼저 사람별로, 집, 사무실 위치 중 작은 값과 큰 값을 관리합니다.(Ex: 작은 값을 집의 위치로 변경함)
2. 철로의 시작은 항상 누군가의 집 위치(1에서 관리한 작은 값)가 되어야 합니다.
   1. 집 위치가 아니라면, 삐져나온 만큼을 이동시켜 다른 사람을 추가로 포함시키거나, 포함시킬 대상이 없더라고 그 값과 같습니다.
3. 따라서 주어진 집의 위치들을 정렬합니다.
4. 왼쪽부터 차례대로 모든 집에 대해 (집의 위치 + d) = A라고 칭하면, 집의 위치가 기준이 되는 집의 위치보다 크거나 같고, 사무실의 위치가 A보다 작거나 같은 사람들의 수를 구합니다.
5. 하지만 O(N²)의 시간복잡도가 발생합니다.
6. 3번과 반대로, 사무실을 기준으로 다시 정렬합니다.
7. 사무실의 위치가 4에서 구한 A보다 작거나 같은 사람들을 구합니다.
8. 다시 발생한 문제는 다음 사람의 집의 기준으로 변경이 되면, 다음 기준이 되는 집보다 왼쪽에 집이 있는 사람은 대상에서 빠져야 합니다.
9. 우선순위 큐를 이용하여 집의 위치가 기준의 집의 위치보다 작은 것들을 삭제합니다.
10. 위 작업들을 반복하여 큐에 몇 명의 사람이 들어가 있는지를 파악합니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
#define N 100000
#define F first
#define S second
using namespace std;
typedef pair<int,int>P;
int n,m,i,j,e[N],a;
priority_queue<P,vector<P>,greater<P>>q;
P d[N];
int c(P a,P b){return a.S<b.S;}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(;i<n;i++){
        cin>>d[i].F>>d[i].S;
        if(d[i].F>d[i].S)swap(d[i].F,d[i].S);
        e[i]=d[i].F;
    }
    cin>>m;
    sort(e,e+n);
    sort(d,d+n,c);
    for(i=0;i<n;i++){
        while(j<n&&e[i]+m>=d[j].S)q.push(d[j++]);
        while(!q.empty()&&q.top().F<e[i])q.pop();
        a=max(a,(int)q.size());
    }
    cout<<a;
}