[BOJ] 1931번 회의실 배정

문제 바로가기

접근

처음에는 회의 종료시간을 기준으로만 정렬을 했었는데, 반례를 찾다보니 같은 종료시간 내에서도 시작시간이 빠른 순으로 정렬을 해야 한다는 걸 알게 되었다.
예를 들어 정렬 후 (1,4), (2,4), (3,4), (4,4), (4,4)가 되면 선택할 수 있는 회의는 (1,4), (4,4), (4,4)이다. 시작시간과 종료시간이 같을 수 있다고 했으므로 시작시간으로 한번 더 정렬하지 않으면 일부 회의들을 놓칠 수 있다.

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

#define MAX 100000

bool comparator(const pair<int,int>& a, const pair<int,int>& b) {
  if(a.second == b.second)
    return a.first < b.first;
  return a.second < b.second;
}

int main() {
  std::ios::sync_with_stdio(false);
  int N;
  int end, cnt = 0;
  pair<int,int> timetable[MAX];

  cin >> N;

  for(int i = 0; i < N; i++)
    cin >> timetable[i].first >> timetable[i].second;
  sort(timetable, timetable + N, comparator);

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

  cout << cnt;
}