문제 1931 ( C++)

그리디 알고리즘 문제

 

회의실 배정 문제로 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는 문제

 

 

문제 풀이

 

그리디 알고리즘의 정의를 다시 생각해보면

 

현 상황에서 가장 최적의 선택을 하는 알고리즘이 그리디 알고리즘.

 

이 점을 이용할 수 있도록 주어진 N 개의 시작시간, 종료시간 쌍을 정렬하자.

 

algorithm 라이브러리를 include 하여 sort 함수를 이용하면 쉽게 정렬이 가능하다.

 

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

v 는 N개의 회의시간 정보를 담고 있는 벡터이다.

 

cmp는 어떤 방식으로 정렬할지 sort 함수에 알려주는 함수이다.

typedef struct pair {
  int start;
  int end;
} Pair;


bool cmp(Pair f, Pair t) {
  if ( f.end == t.end )
    return f.start < t.start;
  else
    return f.end < t.end;
}

 

N 개의 회의시간 정보를 저장할 객체 pair 를 생성하고 객체 pair를 이용하여 cmp를 만든다.

 

cmp 함수는 인자로 받은 두 개의 pair 객체의 end 시간이 같다면 시작시간(start)이 적은 객체를, end 시간이 다르다면 end 시간이 적은 객체를 앞에 배치되도록 정렬시키는 함수이다.

 

위 cmp 함수를 sort 함수의 세 번째 인자로 전달하여 N개의 회의시간 정보를 정렬한 뒤 마지막으로 선택한 회의 i의 종료시간보다 시작시간이 더 큰 회의를 선택하고 선택된 회의의 개수를 찾아 출력하면 끝.

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct pair {
  int start;
  int end;
} Pair;

bool cmp(Pair f, Pair t) {
  if ( f.end == t.end )
    return f.start < t.start;
  else
    return f.end < t.end;
}

int main(void) {

  int N;

  cin >> N;

  vector<Pair> v(N);

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

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

  int cnt = 0;
  int n = 0;

  for (int i = 0; i < v.size() ; i++ ) {
    if ( n <= v[i].start ) {
      n = v[i].end;
      cnt++;
    }
  }
  cout << cnt;

  return 0;
}

 

 

결과