[C++] 백준 1931 : 회의실 배정

#include <iostream>
#include <vector>
#include <utility> // pair
#include <algorithm> // sort

using namespace std;

int N;
int maxNum = 0;
vector<pair<int, int> > v;

int main(int argc, char** argv){
  scanf("%d", &N);
  
  int a, b;
  for(int i=0; i<N; i++){
    scanf("%d %d", &a, &b);
    v.push_back({b, a}); // 종료 시간으로 기준점을 잡아야한다. 종료시간을 짧게 잡아야 많이 회의 가능
    // 시작 지점을 기준으로 정렬하면 너무 많은 반복문을 돌아야한다.
  }

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

  int end = v[0].first; // 마지막 종료 시간  - 1번째 골라두고 시작
  int cnt = 1; // 골라지는 수 세기

  for(int i = 1; i < N; i++){
    if(end <= v[i].second){
      end = v[i].first;
      cnt++;
    }
  }

  printf("%d", cnt);

  return 0;
}

처음에는 회의실 배정을 시작 빠른 순서로 정렬시켜서 틀렸는데
반대로 생각해보는 것이 중요한 듯 하다.

끝나는 순서가 빠른 것들을 열심히 골라주면 그냥 그것이 답이다... 원래 그런건가 아니면 테스트 케이스가 부족해서 그런건지. 아무튼 제대로 된 알고리즘은 아니라고 생각함.