[백준] 1931. 회의실배정 (C++)

문제 : www.acmicpc.net/problem/1931

1931번: 회의실배정

 

풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool SortSecCol(const vector<int>& v1, const vector<int>& v2)
{
    return v1[1] < v2[1];
} // 두번째 열 기준으로 오름차순 정렬
 
int main() {
    int n;
    int count = 0;
    int start = 0;
    cin >> n;
 
    vector <vector<int>> time(n, vector<int>(2, 0)); // n행 2열을 가지는 벡터 선언
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> time[i][j];
        }
    } // 회의 입력
 
    sort(time.begin(), time.end()); // 시작 시간이 빠른 순서대로 정렬
    sort(time.begin(), time.end(), SortSecCol); // 회의 종료시간이 짧은 순서대로 정렬
 
    for (int i = 0; i < n; i++) {
        if (time[i][0] >= start) {
            count++;
            start = time[i][1]; // 시작은 회의의 종료시간으로
        }
    }
 
    cout << count;
    return 0;
}
 

 

시작 시간이 빠른 순서대로 정렬 후, 회의 종료시간이 짧은 순서대로 정렬해놓은 후 전 회의의 종료시간 보다 다음 시작하는 회의의 시작시간이 클 경우에 카운팅해가면 답을 찾을 수 있다.