[C++] 백준 1931번: 회의실 배정

🔗 문제

 

1931번: 회의실 배정

1931번: 회의실 배정

 

🖍 풀이

 

✔️ 최적의 해를 구하는 방법 
회의가 끝나는 시각으로 정렬한 후, 다음 회의 시작 시각보다 같거나 큰 회의를 잡는다.

 

 

회의가 언제 시작했던 빨리 끝내야 뒤에 시간이 많다는걸 생각해내면 된다.

• 시작 시각으로 정렬한 후 가능한 회의 개수는 3개 (오답)
• 종료 시각으로 정렬한 후 가능한 회의 개수는 4개 (정답)

 

---

 

시작 시각과 끝나는 시각을 std::pair<int, int>로 저장했다.

종료 시각이 같다면 시작 시각이 빠른 걸로 선택할 수 있도록 정렬하기 위해 비교 함수를 커스텀해줘야 한다. 

bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b)
{
    if(a.second == b.second)
        return a.first < b.first;
    
    return a.second < b.second;
}

• 정렬 기준 1순위: 종료 시각을 오름차순
• 정렬 기준 2순위: 시작 시각을 오름차순

 

💾  소스

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

bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b)
{
    if(a.second == b.second)
        return a.first < b.first;
    
    return a.second < b.second;
}

int main()
{
    int N, answer;
    int start, end;
    std::vector<std::pair<int, int>> time;

    //input
    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        std::cin >> start >> end;
        time.push_back({start, end});
    }
    

    //solve
    std::sort(time.begin(), time.end(), compare);

    end = time[0].second;
    answer = 1;
    for(int i=1; i<N; ++i)
    {
        if(end <= time[i].first)
        {
            end = time[i].second;
            ++answer;
        }
    }

    //output
    std::cout << answer;

    return 0;
}