백준 - 2170 선 긋기

문제 링크입니다 : https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

라인 스위핑 유형이라는데, 그리디 알고리즘 같기도하다.

 

라인 스위핑에 대해 알아봐야겠다.

 

 

 

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

using namespace std;

int main() {

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

    int N;
    cin >> N;
    vector<pair<int, int>> lines(N, pair<int, int>());
    for(int i = 0; i < N; i++) {
        cin >> lines[i].first >> lines[i].second;
    }

    sort(lines.begin(), lines.end());


    int end = lines[0].second;
    int len = lines[0].second - lines[0].first;
    for(int i = 1; i < N; i++) {
        int curStart = lines[i].first;
        int curEnd = lines[i].second;
        if(end >= curStart) {
            if(end >= curEnd) continue;
            len += curEnd - end;
        } else {
            len += curEnd - curStart;
        }
        end = (curEnd > end) ? curEnd : end;
    }

    cout << len;

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~