[백준] 19598 최소 회의실 개수

문제 :

www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

분석 : 

이 문제는 주어진 인풋에 대해 필요로 되는 최소 회의실 개수를 구하는 문제다. greedy를 이용해 풀었고

회의실이 3개, 회의실 이용 시간은

0 40

15 30

5 10 으로 주어질 때 

 

1. 회의 시작 시간을 기준으로 정렬을 한다. 

0 40

5 10

15 30 

 

함수 안에서 처음에 0, 40을 vv vector에 담은 뒤 v 함수 다 돌 때까지 vv 크기만큼 if문을 돌게된다.

else 문 -> 다음 회의 시작 시간(iter.first)이 vv vector에 담긴 원소의 회의 끝나는 시간(vv[i].second)보다 클때만 다음 회의의 끝나는 시간을 업데이트 해준다. 그게 아니라면 continue로 넘기게 된다.

vv 크기만큼 다 돌게 되면 다음 if 문이 실행된다. 

이 부분은 연장되지 않은 회의를 vv에 누적시켜 새로운 회의실 필요한 경우 넣는 곳이다.

vv vector에는 최종적으로 누적된 회의만이 저장되어 있다. ex> 0 40 / 5 30 

앞에 1931번을 먼저 풀고 이 문제를 풀길 추천한다 !! 

 

 

C++ 코드 : 

//
//  19598_room_min.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/10.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int assign_room_min(int n, vector <pair<int, int>> v){
    int cnt;
    
    vector<pair<int, int> > vv;
    sort(v.begin(), v.end()); // first 원소 기준으로 오름차순을 정렬
    
    vector<pair<int, int> >::iterator  iter;
    
    for(iter = v.begin(); iter != v.end(); ++iter){
          int i = 0;
          for(i = 0; i < vv.size(); i++) // 검사할 갯수 0번째부터 검사 시작
          {
              if((*iter).first >= vv[i].first && (*iter).first < vv[i].second){
                  continue;
              }
              else {
                  vv[i].second = (*iter).second;
                  break;
              }

          }
          
          if(i ==  vv.size()){
              vv.push_back(*iter);// 처음 넣는 곳
          }
              
      }
    
    cnt = (int)vv.size();
    return cnt;
}

int main(){
    int n;
    cin >> n;
    vector <pair<int, int>> v;
    int start, finish;
    for(int i = 0; i < n; i++){
        cin >> start >> finish;
        v.push_back(make_pair(start, finish));
    }
    int count = assign_room_min(n, v);
    cout << count << endl;
    return 0;
}