[백준] 1931 회의실 배정

문제 : 

www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

분석 : 

이 문제는 대표적인 greedy algorithm으로 푸는 문제이다. 회의실, 가방 배낭 등 고전적인 문제 유형인거 같다.

벡터에 인풋값을 모두 담은 뒤 핵심은 회의가 끝나는 시간 second 를 기준으로 정렬을 하는 것이었다. 그리고 for문을 돌면서 검사하는데 이전 회의의 끝나는 시간 < 다음 회의 시간 이면은 회의가 시작 될 수 있는 것이므로 cnt 값을 증가시켜 회의의 갯수를 셌다. 

 

c++ 코드 :

//
//  1931_room.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/10.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;



int assign_meeting_room(int n, vector<pair<int, int>> v){
    int cnt = 1; // 제일 빨리 끝나는 거 일단 넣어 놓기
    
    sort(v.begin(), v.end(), [](auto &left, auto &right) { // second 순으로 정렬
        if(left.second == right.second){
            return left.first < right.first;
        }
        return left.second < right.second;
    });
    
    int before_meet = 0;
    for(int i = 1; i < (int)v.size(); i++){
        if(v.at(i).first >= v.at(before_meet).second){
            cnt++; //put meeting
            before_meet = i;
        }
    }

    
    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));
        //cout << v[i].front().first << v[i].front().second << endl;
    }
    int count = assign_meeting_room(n, v);
    cout << count << endl;
    return 0;
}