[백준] 1931 회의실 배정 👩‍💻

• 백준 # 1931 회의실 배정
• 사용 언어 : C++
• 난이도 : 실버Ⅰ🥈

문제

N개의 회의실에 대해 회의 시작시간과 끝시간이 주어진다. 회의시간이 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구하라.

분석

이 문제에는 각 회의의 시작 시간과 끝 시간만이 있을 뿐, '몇시 이후에는 회의실 자체를 사용할 수 없다'라는 조건은 존재하지 않는다. 그저 주어진 회의중 가장 많은 회의를 할 수 있게 만들면 될 뿐!

그렇다면 회의를 가장 많이하려면 어떤 회의들을 선택해야할까? 문제에서 주어진 회의의 시작 시간, 끝 시간, 회의의 지속 시간을 어떻게 활용해야 할 지 생각해보자.

회의를 아무리 빨리 시작해도, 늦게 끝나게 된다면, 그 기간에 존재하는 다른 회의들은 못하게 된다.

만약 (1,10),(2,5),(6,8)인 회의 3개가 있다고 가정하자.
(1,10)인 회의를 선택한다면, 시작시간이 매우 빠르지만 10시에 끝나기 때문에 나머지 두 회의는 하지 못한다.
반면, 끝나는 시간이 가장 빠른 (2,5)를 선택한다면, 그 다음으로 (6,8)인 회의를 할 수 있다.

따라서, 최대한 많은 회의를 실행하기 위해서는 최대한 빨리 끝나는 회의를 선택해야 한다.

풀이

위의 두 조건을 이용해 문제를 풀어보자. 우선, 끝나는 시간이 빠른 회의가 우선적으로 선택되어야 한다. 따라서, 모든 회의를 끝나는 시간이 빠른 순으로 정렬한다.

두번째 조건에 의하면, 최대한 빨리 끝나는 회의 중에서도, 앞 회의의 끝시간과 차이가 가장 적어야 한다. 따라서, 끝나는 시간이 같다면, 시작 시간이 가장 빠른 순으로 회의를 정렬한다.

예시

1,4
3,5
0,6
5,7
3,8
5,9
6,10
8,11
8,12
2,13
12,14

정렬이 완료되었다면, 끝나는 시간이 가장 빠른, 첫번째 회의를 선택한다.
그 후, 다음 회의를 조회하며, 시작시간이 첫번째 회의보다 늦거나 같은 회의를 찾는다. 그 후, 다시 그 회의의 끝 시간을 기준으로, 시작 시간이 그 시간보다 늦거나 같은 회의를 찾는 것을 반복한다.

예시의 경우는 아래와 같은 과정을 거친다.

(1,4)를 선택 : 끝 시간- 4
끝 시간이 4보다 늦거나 같은 회의 선택 : (5,7)
끝 시간이 7보다 늦거나 같은 회의 선택 : (8,11)
끝 시간이 11보다 늦거나 같은 회의 선택 : (12,14)

우리는 어떠한 회의가 선택되었는지를 찾는게 아니라, 최대로 실행할 수 잇는 회의의 '개수'를 찾는 것이다. 따라서, 조건에 맞는 회의를 찾을 때마다 cnt 변수를 1 증가하는 방식으로 수행하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<pair<int,int>> meetingTime;
int i=0;
int cnt=0;
int endTime; // 탐색 시작 끝 범위 

bool compare(pair<int,int>a,pair<int,int>b);


int main()
{
    cin >> N;
    
    for(i=0;i<N;i++){
        int start,end;
        cin>>start>>end;
        meetingTime.push_back(pair<int,int>(start,end));
    }
    
    // 종료시간 기준 오름차순으로 정렬
    sort(meetingTime.begin(), meetingTime.end(),compare);
    
    // 첫번째 회의 선택 - 종료시간 설정
    endTime = meetingTime[0].second;
    cnt ++;

    for(i=1;i < N; i++){
    	// 현재 회의의 시작시간이 이전 회의의 종료시간보다 늦거나 같으면 선택 
        if(endTime <= meetingTime[i].first){
          cnt++;
          endTime = meetingTime[i].second;
        }
       
    }
    
    cout << cnt;

    return 0;
}

// 회의 정렬 함수 
bool compare(pair<int,int>a,pair<int,int>b){
	// 종료시간 같으면 시작시간 빠른 순으로 
    if (a.second == b.second) 
        return a.first < b.first;
    // 종료시간 다르면 종료시간 빠른 순으로 
    else 
        return a.second < b.second;
}

느낀점

문제에서 주어진 요소들을 어떻게 활용할 것인지를 잘 정했어야 하는 문제! 지금처럼 예시 분석을 잘 해나가면 될듯 하다:)