(1931) 회의실 배정

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

단계별로 풀어보기

23단계(그리디 알고리즘) 2번째

 

 

 

어떤 순간에 가능한 회의가 (s1,e1), (s2,e2) 두 개 있다고 하자. 이때 첫번째 회의를 하면 다음 회의는 e1부터 시작할 수 있고, 두번째 회의를 하면 다음 회의는 e2부터 시작할 수 있다. 즉 e1과 e2 중 작은 값을 갖는 회의를 하는 것이 다음 회의 가능 구간이 넓어지므로 항상 이득이다. 따라서 모든 회의를 종료 시간에 대해 오름차순으로 정리한 뒤, 순차적으로 탐색하며 회의가 가능한 경우(이전 회의가 끝난 시간보다 지금 회의가 시작하는 시간이 뒤에 있는 경우) 회의를 하고 아니라면 넘기면 가능한 회의의 수를 계산할 수 있다.

주의할 점은 시작 시간과 종료 시간이 같은 입력이 들어온다는 점이다. (s1,e1), (e1,e1) 두 회의가 있을 때 첫번째 회의를 끝내고 두번째 회의를 하는 것은 가능하지만 반대의 경우는 불가능하다. 따라서 이런 경우 시작 시간이 빠른 회의가 먼저 들어올 수 있도록 해야 한다.(이 케이스를 고려하지 않아 몇 번 틀렸다.)

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<long,long>> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i].first >> v[i].second;
  
  sort(v.begin(), v.end(), [](auto A, auto B){
    if(A.second!=B.second)  return A.second<B.second;
    return A.first<B.first;
  });
  
  int ans= 0;
  long s= 0;
  
  for(auto elem:v){
    if(s>elem.first)  continue;
    
    s= elem.second;
    ans++;
  }
  
  cout << ans;
  
  return 0;
}