[백준] 1931.cpp : 회의실배정

www.acmicpc.net/problem/1931

1931번: 회의실배정

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

int n;
vector<pair<int, int>> v; // 자료형 주의!!

// 입력한 회의 시간들을 정렬해주는 기준함수
bool desc(pair<int, int> p, pair<int, int> p2)
{
  // 종료 시간이 같을 경우 시작시간 빠른 순
  if(p.second == p2.second)
  {
    return p1.first < p2.first;
  }
  // 종료 시간이 빠른 순
  return p.second < p2.second;
}

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  v.reserve(n);
  unsigned int l,r;
  for(int i = 0 ; i < n ; i++)
  {
    cin >> l >> r;
    v.emplace_back(pair<int, int>(l, r));
  }
  sort(v.begin(), v.end(), desc);

  int cnt = 1;
  int idx = 0; // 이전에 시작한 회의
  // 쭉 한번 돌면서 이전의 회의가 종료 되었으면 가장 앞에 있는 회의를 실행
  for(int i = 1 ; i < n ; i++)
  {
    if(v[i].first >= v[idx].second)
    {
      idx = i;
      cnt++;
    }
  }
  cout << cnt << '\n';
}

 

[Try]

1. 일단 완전탐색을 돌려야 할 것 같은데 재귀적으로 호출하든 안하든 시간이 문제가 될 것 같다. 그리디 알고리즘으로 풀면 반례가

     있다고 생각해서 혹시 몰라 분류를 봤더니 역시나 그리디.. 1 - 3 / 3 - 10 vs 2 - 4 / 4 - 5 / 5 - 6 과 같이만 돼있어도 실패인데..흠

     잘못 생각하고 있었다. 먼저 시작하는 순으로 이어지는 것이 아니라 가장 빨리 끝나는 순으로 이어주면 된다. 대박

2. 탐색하는 부분은 O(n) 인 것 같은데.. 정렬 쪽이 문제가 되나?

     일단 코드 자체는 복잡하게 max idx end 등을 다 두지 말고 idx 하나로 값을 참조하면서 처리하고 while 말고 for 루프로 돌리자

3. 종료 시간이 같을 경우에는 시작 시간을 기준으로 정렬을 해주어야 한다!

 

[Point]

1. 그리디 알고리즘을 생각했는데 시작 시간으로밖에 떠올리지 못했다. 발상의 전환!

2. 2의 31승이니까 int 도 가능하다... 문제 똑바로 읽도록 하자

3. 입력값은 unsigned 로 받아놓고 pair 에는 int 로 바꿔 저장했다. 미련한 짓 하지 말자 ㅠㅠㅠㅠ