[BOJ] 15922번 : 아우으 우아으이야!!(C++)

문제 링크 : 백준 15922번

[문제 접근]

1. 먼저 x좌표가 작은 순으로 정렬해준다.
2. 첫 선분을 start, end에 대입해주고 i=1부터 탐색한다.
3. 전 선분의 end값이 현재 선분의 start값보다 크다면 선분이 겹치는 경우 이므로 전 선분의 end값과 현재 선분의 end값 중 큰 값을 end로 지정해준다.
4. 그 외의 경우는 겹치지 않는 선분이므로 ans에 선분의 길이를 더해주고 start, end값을 현재 선분으로 갱신시킨다.
5. 탐색을 마치고 마지막으로 남은 선분의 길이를 ans에 더해준다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n;
vector<pair<int, int> > arr;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        int a,b;
        cin >> a >> b;
        arr.push_back({a,b});
    }
    sort(arr.begin(), arr.end());
    
    int ans = 0;
    int start = arr[0].first, end = arr[0].second;
    for(int i=1 ; i<n ; i++) {
        int x1 = arr[i].first, x2 = arr[i].second;
        if(end>x1) {
            end = max(end, x2);
        } else {
            ans += end-start;
            start = x1, end = x2;
        }
    }

    ans += end-start;
    

    cout << ans;

    return 0;
}