[C/C++][Greedy] 백준 2170번: 선 긋기

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

그리디 알고리즘 문제이다.

조건 :

선을 그을 때 start, end가 주어지고 중복되게 그린 부분은 중복해서 길이에 합산하지 않는다.

첫 줄에 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

다음 N개의 줄에 두 점의 위치 x,y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

그려진 선의 총 길이 구하기.

x가 y보다 작다고 조건에 명시되어 있으므로 시작점과 끝점은 정렬하지 않아도 된다.

선이 중복되게 그려지는 경우는 먼저 선이 그려진 이후 시작점과 끝점 사이에 (start <= K <= end) 다른 선분의 시작점 또는 끝점이 오면 중복되게 그려진다. 따라서 선분의 시작점과 끝점사이에 다른 선분이 오는지 체크해야한다.

그리고 중복되게 그려진 이후 그 중복되게 그린 선이 본래 존재하던 선보다 더 길 수도 있기 때문에 본래 있던 선분의 시작점과 끝점을 수정해야한다.

그리고 떨어져 있는 모든 선을 구분하기 어렵기 때문에 시작점을 기준으로 정렬하여 가까운 선들을 먼저 중복되게 그리게 만들어야 한다.

조건은 본디 존재하던 start와 end사이에 다른 선분의 start 또는 end가 존재하는가 존재하지 않는가로 구분하고

1. 존재할 경우 현재 그려진 선의 end를 새로 그리는 선의 end로 수정한다.

1. 존재하지 않을 경우 answer에 지금까지 그려진 선의 총 길이를 더하고, 현재 그릴 선의 start와 end를 지금 그리는 선의 start와 end로 고친다.

반복문이 끝날 경우 마지막 선이 그려진 길이를 더해서 출력한다.

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

struct Line{
  int start, end;
};

Line arr[1000001];
int N;

bool compare(Line a, Line b){
  if(a.start == b.start){
    return a.end < b.end;
  }
  return a.start < b.start;
}
int main(){
  cout.tie(NULL);
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  //
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> arr[i].start >> arr[i].end;
  }
  sort(arr, arr+N, compare);

  int answer = 0;
  int mini = arr[0].start;
  int maxi = arr[0].end;
  for(int i=0; i<N; i++){
    if(arr[i].start<=maxi){
      maxi = max(maxi, arr[i].end);
    }
    else{
      answer += maxi - mini;
      mini = arr[i].start;
      maxi = arr[i].end;
    }
  }
  answer += maxi - mini;
  cout << answer ;
}