2021. 3. 6. 21:44ㆍAlgorithm
문제
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;
}