[백준] 1931 회의실 배정

문제

www.acmicpc.net/problem/1931

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

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

 

---

문제 요약 

하나의 회의실을 시간이 겹치지 않게 최대한 많은 수의 회의를 진행 해야 한다.

 

조건 해석

1. 회의는 한번 시작하면 중간에 중단된 수 없다 == 시간이 겹치면 안된다.

2. 끝남과 동시에 회의가 시작될 수 있다. == i번째 회의의 끝나는 시간과 i+1 번째 회의의 시작하는 시간은 같아도 된다.

3. 시작시간과 끝나는 시간이 같을 수도 있다. == 시작하는시간과 끝나는 시간이 같으면 무조건 진행 가능.

 

접근

문제의 어떤 요소를 가지고 그리디 알고리즘을 적용해 나갈지가 중요하다.

 

실수1 :

그리디 알고리즘 으로 회의 시간이 짧지만, 배정된 회의 와 겹치지 않게 배정하려 했다.

단순히 회의 시간(끝나는시간-시작시간) 으로 오름차순 정렬후 배정 하게 된다면.

회의실 배정시 고려해야 할 사항이 늘어나고, 구하기 어렵다.

모든 이미 배정된 회의실들의 시작 시간, 종료 시간을 모두 비교 후 겹치지 않을 경우에만 배정 가능해 진다.

 

이와같은 비효율을 제거하기 위한 접근 방법은,

종료 시간 순으로 정렬하는 것이다.

가장 빨리 끝나는 회의와 가장 늦게 끝나는 회의는 고정되어 있으므로 그 시간 사이에서

시간이 겹치지 않게(조건1) 가장 빨리 끝나는 회의를 선택해 나가면 쉽게(조건 2)

가장 많은 회의들을 배정 할 수 있다.

 

또한 배정된 회의와 겹치지 않게할 기준선을 now 라는 변수를 만들어

배정된 회의의 끝나는 시간을 넣어준다.

시작시간이 now 보다 크거나 같을 시(조건3)에 만 회의를 배정하고 now 를 갱신한다.

 

문제 예시- 그림 묘사.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class room
{
public:
    int start;
    int end;
public:
    //생성자
    room(const int start_ = 0, const int end_= 0)   
    {
        initalization(start_,end_);
    }
    room(const room& input)   
    {
        initalization(input.start,input.end);
    }
    //초기화 함수
    void initalization(const int start_,const int end_)
    {
        start = start_;
        end = end_;
    }
    //정렬을 위한 연산자 오버로딩
   friend bool operator < (const room& r1, const room& r2)
   {
       //끝나는 시간이 같다면,시작 시간이 빠른순
       if(r1.end == r2.end)
            return r1.start<r2.start;
        //끝나는시간이 빠른순 정렬
        return r1.end<r2.end;
   }
   //입력 연산자 오버로딩
   friend istream&  operator >> (istream& in,  room& r)
   {
       in >> r.start >> r.end;
       return in;
   }
};
int main()
{
    int n;
    cin >> n;

    vector<room> rooms(n);
    for(int i = 0 ; i<n;i++)
    {
        cin >> rooms[i];
    }
    //정렬
    sort(rooms.begin(), rooms.end());

    int count = 0;
    //겹치지 않는 기준 설정
    int now = rooms[0].end;
    count++;

    for(int i = 1 ; i<n;i++)
    {
        // 만약 시작시간이 기준보다 크거나 같으면 - 겹치지 않음
        if(rooms[i].start >= now)
        {
            count++;
            now = rooms[i].end;
        }
           
    }
    cout << count;
}