겹치는 선분

Problem link: https://www.acmicpc.net/problem/1689

간단한 라인스위핑 문제이다.

모든 선분을 opening / closing 두 개의 점으로 나누어 저장한 뒤 정렬하고, 스위핑을 진행한다.

누적된 opening의 수가 최대가 되는 지점을 찾으면 된다.

단, 이때 끝점 겹침 조건을 만족시켜주기 위해서 동일 위치에 대해서는 닫히는 선분을 먼저 처리하도록 정렬 시 조치한다.

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

using namespace std;

size_t N;
vector<pair<int, bool> > POINTS;

size_t Solve(void)
{
  sort(POINTS.begin(), POINTS.end());

  size_t ans = 0;
  size_t opened = 0;
  for (const auto& p : POINTS)
  {
    if (p.second)
    {
      ++opened;
      ans = max(ans, opened);
    }
    else
    {
      --opened;
    }
  }

  return ans;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Inputs
  cin >> N;
  for (size_t it = 0; it < N; ++it)
  {
    int s, e;
    cin >> s >> e;
    POINTS.emplace_back(s, true);
    POINTS.emplace_back(e, false);
  }

  // Solve
  cout << Solve() << '\n';

  return 0;
}