[BOJ/백준][Gold3] 1689 : 겹치는 선분 (C++)

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

1689번: 겹치는 선분

 

[난이도] Gold3
[유형] Greedy,Sweeping

[풀이]
1. 각 점의 시작점은 s, 끝점을 e라고 했을 때, pair 배열에 {s,1} , {e,-1}로 각각 저장 뒤
first를 기준으로 정렬한다.
2. cnt를 0으로 초기화 시키고 배열을 앞에서 부터 하나씩 순회하면서 cnt에 second 값을 더해준다.
3. 해당 점을 확인한 순간에 cnt값이 현재 겹쳐져 있는 선의 총 개수이다.
(왜냐하면 선이 시작되면 +1, 끝나면 -1을 해주므로..)

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> a[2000001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int s,e;
        scanf("%d%d",&s,&e);
        a[i]={s,1};
        a[i+N]={e,-1};
    }
    sort(a,a+2*N);
    int ans=0,cnt=0;
    for(int i=0;i<2*N;i++){
        cnt+=a[i].second;
        ans=max(cnt,ans);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/1689.cpp