백준 1931번: 회의실 배정

문제 링크 : https://www.acmicpc.net/problem/1931

1931번: 회의실배정

 

 문제설명 

첫째줄에 회의의 수N이 주어지고 그다음줄부터 N개의 회의 시작시간과 종료 시간이 주어딘다

이때 회의를 진행 할 수 있는 경우의수중 가장 큰 경우는 ?

 

처음에 어떻게 해야될지 몰라서 30분 고민하다가 그냥 인터넷 찾아봤다.

배낭 문제처럼 유명한 문제라고한다

 

 알고리즘 

 

1. 종료시간이 빠른 회의 부터 진행 ->진행 가능한 회의 중 빨리 끝나는거 진행 -> .... -> 총 진행한 회의수 출력 .

 

 코드 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main() {
 
    vector < pair<long long, long long>>  p;
 
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        p.push_back(make_pair(b, a));
    }
 
    //종료시간 기준 오름차순 정렬
    sort(p.begin(), p.end()); 
 
    //처음 진행하는 회의는 무조건 하니까 1부터 시작
    int result = 1; 
    int num = p[0].first;
 
    for (int i = 1; i < N; i++) {
        //진행 가능한 회의중 회의 진행이 가장 빨리끝나는 회의를 진행
        if (p[i].second >= num) {
            num = p[i].first;
            result++;
        }
 
    }
    cout << result;
}