[Algorithm] Baekjoon 2170번 : 선 긋기

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

2170번: 선 긋기

struct Node
{
    int start;
    int end;
};
 
vector<Node> nodes;
int n;
 
bool cmp(const Node& a, const Node& b)
{
    return a.start < b.start;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        Node node;
        cin >> node.start >> node.end;
        nodes.push_back(node);
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    int start = nodes[0].start;
    int end = nodes[0].end;
    int answer = 0;
 
    for (int i = 1; i < nodes.size(); ++i)
    {
        if (nodes[i].start <= end)
        {
            if (end < nodes[i].end)
            {
                end = nodes[i].end;
            }
        }
        else
        {
            answer += end - start;
            start = nodes[i].start;
            end = nodes[i].end;
        }
    }
 
    cout << answer + end - start;
 
    return 0;
}

프로그래머스에서 호텔 대실문제를 풀다가, 관련되서 내가 잘 모르는부분이 있다는 것을 깨닫고 알아보다가 라인스위핑이란 풀이방법이 있다는것을 인지. 대표적인 문제로 이 선긋기 문제가 나와서 풀어봤다.

이걸 다시 호텔대실문제에 대입해봐야겠다.