[C/C++] 백준 1931: 회의실 배정 (풀이)

1931: 회의실 배정 문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

 이 문제는 Greedy 알고리즘 중에서 제일 유명한 문제라고 할 수 있다. 한개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의 중에 회의실을 사용할 수 있는 회의의 최대 개수를 구하면 된다.

 

 결론부터 말하자면 끝나는 시간이 제일 빠른 회의부터 차례대로 진행할 때 회의의 개수가 최대가 된다. 각 경우마다 가장 이득이 되는 선택을 하면 되는데 그 각각의 선택이 전체적으로도 가장 이득이 되는 대표적인 예이다.

 

 구현은 끝나는 시간 순서대로 오름차순으로 정렬을 한다. 이때 한가지 주의해야할 점은 회의의 시작시간과 끝나는 시간이 같을 수도 있기 때문에 끝나는 시간이 같다면 시작하는 시간도 오름차순으로 정렬해줘야한다. 만약 이 조건이 없었다면 끝나는 시간이 같을 경우, 시작하는 시간은 아무런 관계가 있지 않기 때문에 시작하는 시간은 오름차순으로 정렬하지 않아도 된다. 

 

 이차원 vector v1에 시작시간-끝나는 시간을 저장한 뒤 오름차순으로 정렬해주었고 while문을 통해 방금 끝난 회의의 끝나는 시간보다 같거나 큰 끝나는 회의 중 가장 빠른 회의를 골라서 이것을 반복하면 된다.

 

아래는 전체 소스코드다!

 

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<set>
#include<vector>
#include<string>
#include <map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

bool compare_second(pair<int,int>a,pair<int,int>b)
{
  if(a.second==b.second) //바꾸는게 0
    return a.first<b.first;
  else //가만히 있는게 1
    return a.second<b.second;
}

int main() {    
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  cin>>n;
  vector<pair<int,int>> v1;
  vector<int> v2;

  for(int i=0;i<n;i++)
    {
      int tmp1,tmp2;
      cin>>tmp1>>tmp2;
      v1.push_back(make_pair(tmp1,tmp2));      
    }
  sort(v1.begin(),v1.end(),compare_second);

  int finish_time=v1[0].second;  
  int cnt_meeting=1,array_index=0;
  while(1)
    {
      int k=0;
      for(int i=array_index+1;i<n;i++)
        {
          if(v1[i].first>=finish_time)
          {
            finish_time=v1[i].second;
            cnt_meeting++;
            array_index=i;
            k=1;
            break;
          }
        }
      if(k==0)
        break;
    }

  cout<<cnt_meeting;

 
  
}