[백준] 골드5 : (2170) 선 긋기

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

 

주어진 입력을 오름차순으로 정렬한다.

 

기준점은 배열의 첫 선분의 끝 점으로 한다.

기준점이 다음 선분의 시작점보다 크거나 같고, 끝 점보다 작을 경우

• 두 선분의 일부가 겹친다는 의미이다.
• 다음 선분의 끝 점에서 기준점을 뺀 값을 결괏값에 더한다.
• 기준점을 다음 선분의 끝 점으로 초기화한다.

기준점이 다음 선분의 시작점보다 작을 경우

• 두 선분이 아예 겹치지 않는다는 의미이다.
• 다음 선분의 끝점 - 시작점을 결괏값에 더한다.
• 기준점을 다음 선분의 끝점으로 초기화한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, Cur, Answer, Start, End;
vector<pair<int, int>> Lines;

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

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> Start >> End;
		Lines.push_back({ Start, End });
	}
	sort(Lines.begin(), Lines.end());

	Cur = Lines[0].second;
	Answer += Lines[0].second - Lines[0].first;

	for (int i = 1; i < Lines.size(); ++i)
	{
		if (Cur >= Lines[i].first && Cur < Lines[i].second)
		{
			Answer += Lines[i].second - Cur;
			Cur = Lines[i].second;
		}
		else if (Cur < Lines[i].first)
		{
			Cur = Lines[i].second;
			Answer += Lines[i].second - Lines[i].first;
		}
	}

	cout << Answer << "\n";
}