[백준 BOJ 1931번] 회의실 배정(C / C++ ) [정렬, 그리디]

1931번: 회의실 배정 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	77651	22885	16534	28.702%

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

예제 입력 1

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

 

예제 출력 1

4

 

풀이

문제의 요점은 회의가 끝난 후 다음 회의와의 텀을 최소화 하는 것이므로 시작하는 시간이 아닌 끝나는 시간을 기준으로 오름차순 정렬을 해줍니다.

pair형 데이터타입은 first 부분을 우선적으로 정렬을 하기 때문에 저는 입력 시에 끝나는 시간을 first에 삽입하였습니다.

그 후 기준점이 되는 변수 end를 선언하여 최초로 끝나는 회의 스케줄의 끝나는 시간을 저장해 준 후 탐색을 시작했습니다.

탐색시에는 현재 가장 빨리 끝난 회의의 끝나는 시간과 그 다음 회의의 시작 시간을 비교했습니다.

어차피 배열은 정렬이 된 상태이므로 가장 처음 조건에 부합하는 다음 회의 스케줄이 가장 텀이 적은 스케줄이므로

카운트를 1 더해준 후 해당 회의 끝나는 시간을 end에 다시 저장을 했습니다.

 

저도 실수한 부분인데 회의가 끝나자마자 다음 회의를 시작할 수 있으므로 조건을 줄 때 주의합니다.

 

코드

// 회의실 배정
#include<bits/stdc++.h>
using namespace std;
pair<int,int>arr[100001];
int main(){
    int n,a,b,cnt=1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>b>>a;
        arr[i]={a,b};
    }
    sort(arr,arr+n); //끝나는 시간을 우선적으로 정렬
    int end=arr[0].first; //최초로 끝나는 회의를 end에 저장해줍시다
    for(int i=1;i<n;i++){
        if(end<=arr[i].second){ //second는 현재 탐색중인 회의 시작시간인데 가장 먼저
        			//조건이 참이 될 때가 가장 텀이 짧을 때 입니다.
            cnt++;
            end=arr[i].first;
        }
    }
    cout<<cnt;
}

 

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정