백준 1931 회의실 배정 / C++

문제 : 1931

풀이 point

그리디를 활용한 문제
회의실을 배정하기 위한 가장 최선의 방법을 찾아야한다.

핵심 포인트는 회의가 빨리 끝나는 값을 선택하는 쪽이 이득이라는 것이다.

회의시간이 가장 빨리 끝나는 것을 선택한다면 그 이후 시작되는 회의들을 선택할 수 있기 때문

ex) 0~5, 3~4가 있을 때 후자를 선택하는 것이 이득
전자를 선택할 경우 4시부터 시작하는 회의는 참석하지 못한다. 그러나 후자는 4시부터 시작하는 회의 참석이 가능하기 때문에 갯수에서 이득을 볼 수 있음

ex2) 0~8, 2~5, 3~4 이때도 세번째를 선택하는 것이 이득

이는 회의시간 이득이 아닌 회의개수를 가장 최대로 만들기 위한 문제이기 때문에 가능

풀이 방법

회의시간이 가장 빨리 끝나는 것을 선택하기 위해 정렬을 해야함 pair를 만들때 첫번째로 오는 값을 회의시작 시간이 아닌 회의끝나는 시간으로 해두면 정렬이 쉬워짐

정렬을 할 때 끝나는 시간이 같으면 시작하는 시간이 빠른 것으로 해야함(시작하자마자 끝나는 회의가 존재하기 때문)

코드

//1931, 회의실 배정

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define end second
#define start first

std::pair<int, int> time[100000]; //end, start
int main(){
    int N;
    std::cin >> N;
    

    for(int i{0}; i<N; ++i)
        std::cin >> time[i].end >> time[i].start;
    

    std::sort(time, time+N);

    int ans{0}; int t{0};
    
    for(int i{0}; i<N; ++i){
        if(t > time[i].end) continue;
        t = time[i].start;
        ++ans;
    }

    std::cout << ans;
    
    return 0;
}

2025-01-11T02:08:00.473Z