백준 1931번 회의실 배정 ( C++ )

문제

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

 

해설

라인스위핑 문제

끝나는 시간을 기준으로 정렬시켜서 풀면 되는 문제

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
int n, ret;
typedef long long ll;
ll start_time, end_time, total_time;
vector<pair<ll, ll>> v;
 
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_time >> end_time;
    v.push_back({end_time, start_time});
  }
  sort(v.begin(), v.end());
 
  total_time = v[0].first;
  ret++;
  for (int i = 1; i < n; i++)
  {
    if (total_time <= v[i].second)
    {
      ret++;
      total_time = v[i].first;
    }
    else
    {
      continue;
    }
  }
 
  cout << ret;
  return 0;
}