# 1931. 회의실 배정

관련 알고리즘 : 그리디, 정렬

 

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

1931번: 회의실 배정

 

---

 

풀이 과정

우선, 문제의 조건을 살펴보면,

1. 회의는 겹칠 수 없음
2. 한 번 시작된 회의는 중단될 수 없음
3. 회의가 끝남과 동시에 다음 회의 시작 가능

이 때 사용할 수 있는 회의의 최대 개수를 구하는 것이므로, 그리디 알고리즘을 사용한다.

문제는 '무엇을 기준으로 그리디 알고리즘을 적용할 것인가' 인데, 

문제의 조건을 통해 고려해보면 강의가 일찍 시작한다 하더라도 늦게 끝나면 강의를 중간에 멈출 수 없기 때문에 그 이후 강의들 또한 늦은 시작시간을 가진 강의들만 추가가 가능하다. 따라서 최대 효율을 내기 위해서는 강의의 시작시간이 아닌, 강의의 종료시간을 기준으로 그리디 알고리즘을 사용해야 한다.

 

즉,

1. 종료시간으로 오름차순 정렬하기
2. 종료 시간이 동일하다면, 그 중 시작 시간이 빠른 순서대로 정렬하기
3. 종료하는 시점보다 큰 시작시간을 가진 회의 선택 후 result+=1 해주기

이런 식으로 문제를 해결할 수 있었다.

 

---

해결 코드 - C++

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

pair<int,int>arr[100001];
int main(){
    int n,end,start,res=1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>start>>end;
        arr[i]={end,start}; // end기준으로 정렬시켜주기 위해 end먼저 삽입
    }
    sort(arr,arr+n); // 종료 시간 오름차순 정렬
    int t=arr[0].first; // 1번째로 끝나는 회의 종료시간 저장
    for(int i=1;i<n;i++){
        if(t<=arr[i].second){ 
            // 이미 정렬된 상태이므로 가장 먼저 조건에 맞는 시작시간이 현재 강의 종료 후 시작되는 가장 빠른 강의
            res++;
            t=arr[i].first; // 갱신
        }
    }
    cout<<res;
}