백준 15922번 아우으 우아으이야!! C++

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

15922번: 아우으 우아으이야!!

 

선분이 (start, end)면 일단 start 기준으로 오름차순 정렬을 한다.

 

그러면 세가지 경우가 있다.

1. 현재 선분이 이전 선분과 모든 부분이 겹치는 경우 -> 아무것도 안해도 됨

2. 현재 선분이 이전 선분가 일정부분 겹치는 경우 -> 겹치는 부분을 제외하고 합을 증가시키고 ge(Global End) 값 갱신

3. 현재 선분과 이전 선분이 겹치지 않는 경우 -> 현재 선분의 길이만큼 합을 증가시키도 ge값 갱신

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;

vector<pair<int, int>> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    v = vector<pair<int, int>>(n);
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        v[i] = { s,e };
    }
    sort(v.begin(), v.end());
    int sum = 0;
    int ge = -1000000001;
    for (int i = 0; i < n; i++) {
        auto curr = v[i];
        if (curr.second <= ge) continue;
        if (curr.first < ge) sum += curr.second - ge;
        else  sum += curr.second - curr.first;
        ge = curr.second;
    }
    cout << sum;
}