[백준] 1931번: 회의실 배정

1931번: 회의실배정

 

회의실 배정 문제에서 중요한 포인트는 이 문제가 그리디 문제라는 것을 깨닫는 것입니다.

 

그리디 문제의 경우, 그리디 문제라는 것을 빨리 파악하는 것이 중요한데요.

이 문제의 경우 각기 다른 시작 시간과 종료 시간을 가진 회의들을 최적으로 배치하는 최적화 문제이므로 그리디임을 파악하기가 그리 어렵지 않았습니다.

 

그렇다면 회의들을 어떤 방식으로 배치해야할까요.

 

1. 회의의 길이로 정렬을 한다 - 시작 시간과 종료 시간이 있기 때문에 이 방식으로는 해결할 수 없습니다.

 

2. 회의의 시작 시간으로 정렬을 한다 - 시작 시간이 빠르더라도 종료 시간이 아주 늦는 경우가 있습니다.

 

3. 회의의 종료 시간으로 정렬을 한다 - 종료 시간이 빠른 순서대로 회의를 배치하는 경우가 최적의 방법이라 할 수 있습니다.

 

 

먼저 회의의 종료 시간을 기준으로 정렬을 하고, 그 정렬된 회의들 중 가능한 회의를 순서대로 배치합니다.

 

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

int N;
int ans = 0;

struct meeting {
  int start;
  int end;
};
vector<meeting> schedule;

void input() {
  cin >> N;
  schedule.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> schedule[i].start >> schedule[i].end;
  }
}

bool cmp(meeting &u, meeting &v) {
  if (u.end == v.end) {
    return u.start < v.start;
  }
  return u.end < v.end;
}

void sortSchedule() {
  sort(schedule.begin(), schedule.end(), cmp);
  
  int end = 0;

  for (int i = 0; i < N; i++) {
    if (schedule[i].start >= end) {
      ans += 1;
      end = schedule[i].end;
    }
  }
}

void printAnswer() {
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  
  input();
  sortSchedule();
  printAnswer();

  return 0;
}