백준 2170 선 긋기 (C++)

2170번: 선 긋기

정렬을 이용한 문제이다. 먼저 입력받은 시작 점과 끝 점들을 오름차순으로 정렬해주었다. 그 후 반복문을 돌며 조건에 맞춰 s와 e를 바꾸어주었다. 조건은 3가지가 될 수 있다.

• 1 4, 3 5 와 같이 일부가 겹처져 있는 경우
• 1 4, 2 3 과 같이 안에 포함되어 겹처져 있는 경우
• 1 4, 5 7 과 같이 겹치지 않는 경우

조건에 따라 합을 구한 후 이를 출력해주었다. 어렵지 않게 풀 수 있는 문제였다.

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

using namespace std;

int N;
vector<pair<long, long>> v;
long result = 0;

void solution() {
    sort(v.begin(), v.end());

    long s = v[0].first;
    long e = v[0].second;

    for (int i = 1; i < N; i++) {
        long ns = v[i].first;
        long ne = v[i].second;

        if (ns <= e) {
            if (ne > e) {
                e = ne;
            }
        }
        else {
            result += e - s;

            s = ns;
            e = ne;
        }
    }

    result += e - s;

    cout << result;
}

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

    cin >> N;

    long a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({ a,b });
    }

    solution();

    return 0;
}