[백준/BOJ] 1931번: 회의실 배정 - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 겹치지 않으면서 가장 많이 열 수 있는 회의의 수를 찾는 문제입니다.

 

최적의 스케줄은 가장 빨리 끝나는 회의 A부터 시작해서, 끝나는 시간이 점점 늦어지는 회의 순으로 진행하는 것입니다.

 

왜냐하면, 끝나는 시간이 더 늦은 다른 회의 B부터 시작했을 경우를 가정해 봅시다.

그럼, 그다음 회의 C는 반드시  B회의가 끝나는 시간 이후부터 시작해야 합니다.

 

그런데, 회의 C는 회의 A의 다음 회의 후보가 되기도 하기 때문에, B로 시작하는 회의의 수가 A로 시작하는 회의의 수보다 많아질 수 없습니다.

 

그래서, 빨리 끝나는 회의부터 늦게 끝나는 회의 순으로 정렬한 후, 겹치는 회의를 제외한 회의 수를 계산하면 됩니다.

 

정렬 방법에 관한 자세한 설명은 여기에  링크해 두었습니다.

[C++] STL sort 함수 사용법

 

이 과정을 소스로 바꾸면 아래와 같이 될 것입니다.

#include <iostream>
#include <algorithm>	// sort 함수 사용
using namespace std;

#define SIZE 100000

typedef struct _meetging{	// 회의 시작 시간과 끝나는 시간을 담는 구조체
    int s, e;
}
MEETING;

MEETING meet[SIZE];

bool compare_meet( const MEETING& a, const MEETING& b){
    if (a.e == b.e){
        return a.s < b.s;
    }
    else{	// 끝나는 시간 오름차순으로 정렬
        return a.e < b.e;
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;  // 회의수
    cin >> N;

    for( int i = 0; i < N; i++){
        cin >> meet[i].s >> meet[i].e;
    }

    // 회의 시간이 끝나는 시간 오름차순으로 정렬
    sort(meet, meet+N, compare_meet);

    int max_m = 0;  // 회의할 수 있는 최대 값

    MEETING first;  // 더미(dummy) 회의
    MEETING& prev = first;

    for(int i = 0; i < N; i++){
        MEETING& me = meet[i];
        if ( prev.e <= me.s){   // 회의 시간이 겹치지 않으면 
            prev = me;
            max_m++;
        }        
    }

    cout << max_m;

    return 0;
}

 

 

소스 코드

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

#define SIZE 100000

typedef struct _meetging{
    int s, e;
}
MEETING;

MEETING meet[SIZE];

int N;  // 회의수
int max_m = 0;  // 회의할 수 있는 최대 값

bool compare_meet( const MEETING& a, const MEETING& b){
    if (a.e == b.e){
        return a.s < b.s;
    }
    else{
        return a.e < b.e;
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;

    for( int i = 0; i < N; i++){
        cin >> meet[i].s >> meet[i].e;
    }

    sort(meet, meet+N, compare_meet);

    MEETING first;
    MEETING& prev = first;

    for(int i = 0; i < N; i++){
        MEETING& me = meet[i];
        if ( prev.e <= me.s){
            prev = me;
            max_m++;
        }        
    }

    cout << max_m;

    return 0;
}