2170, Gold 5

2170번: 선 긋기

문제

• $n(1\leq n \leq 10^{6})$번 수직선 위의 구간 $[x, y], -10^{9}\leq x < y \leq 10^{9}$에 선분을 긋는다
• 그려진 선들의 길이의 합?

 

$O(nlog\ n)$

선분들을 정렬한 후 $O(nlog\ n)$
선분들이 하나의 연속된 그룹(두 선분 사이에 빈틈이 없으면 연속이라 하자)인지 아닌지를 판단한다 $O(n)$

i) $s \leq r$이면 연속

ii) $r < s$이면 불연속

c++

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    vector<pii> v(n);
    for(auto& e: v) cin >> e.first >> e.second;
 
    sort(v.begin(), v.end());
 
    int s, e, res = 0, l = -1e9-1, r = -1e9-1;
    for(auto [s, e]: v){
        if(r < s){
            res += r-l;
            l = s; r = e;
        }
        else{
            r = max(r, e);
        }
    }
    res += r-l;
    cout << res << endl;
 
    return 0;
}cs

 

python3

import sys
 
n = int(input())
d = sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(n)])
l, r = int(-1e9-1), int(-1e9-1)
res = 0
for s, e in d:
    if s <= r: r = max(r, e)
    else:
        res += r-l
        l, r = s, e
print(res+r-l)cs

 

참고

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)