백준 - 2170번 : 선 긋기 (C++)

풀이 방법 : 정렬

선분이 겹치느냐 안겹치느냐에 따라 따로 처리해주면 된다.

이를 처리해주기 위해서 선분의 시작점을 기준으로 오름차순 정렬 해주고,
i-1번째 선분의 끝점이 i번째 선분의 시작점보다 크거나 같은 경우 선분이 겹친 것이고, 그 반대라면 겹치지 않은 것이다.

*겹치지 않았다면 별도의 처리 없이 그 길이만 신경써주면 된다.

선이 겹치는 경우의 케이스를 살펴보면 다음과 같은 경우가 있다.
1. 선분이 다른 선분에 완전히 포함되는 경우
2. 선분이 이어지는 경우

이 두 가지를 다 고려해주기 위해서 i-1번째 i번째 선분을 비교해주면서 두 선분이 겹쳐있는 경우 i번째 선분의 시작점을 두 선분의 시작점 중 더 작은 값으로 업데이트 해주고(처음에 이미 정렬해놨으니 i-1의 시작점으로 처리해주면 된다.) 끝점을 두 선분의 끝점중 더 큰 값으로 업데이트 해줘가면 된다.

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

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;

	cin >> N;

	vector<pair<int,int>> vecLine(N);

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

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

	vector<pair<int, int>> vecAnswer;

	for (int i = 1; i < N; ++i)
	{
		if (vecLine[i - 1].second >= vecLine[i].first)
		{
			vecLine[i].first = min(vecLine[i - 1].first, vecLine[i].first);
			vecLine[i].second = max(vecLine[i - 1].second, vecLine[i].second);

		}

		else
			vecAnswer.push_back(vecLine[i - 1]);
	}

	vecAnswer.push_back(vecLine[N - 1]);

	int Size = vecAnswer.size();

	long long Answer = 0;

	for (int i = 0; i < Size; ++i)
	{
		Answer += vecAnswer[i].second - vecAnswer[i].first;
	}

	cout << Answer;
}