백준 1931 C++ - 회의실 배정

Intro

문제해결 및 소스코드

이 문제는 어떻게하면 최대한 많은 회의를 진행할 수 있을지 찾는문제다.

맨처음 나는 DFS로 접근했으나, 시간초과가 발생했다.

따라서 다른 방식으로 접근하려했다.

1. 문제는 시작시간이 빠른 회의를 고르는것이 아니다.
   • 회의 시작시간이 빨라도 종료되는 시간이 늦으면 최대가 되지 않을수도있기때문.
2. 종료시간이 빠른 회의를 선택해야한다.
   • 회의가 종료되면 종료시간 이후 시작하는 회의 중 가장 빨리 끝나는 회의를 고른다.
3. 종료시간이 같은 회의가 있을경우, 시작 시간이 더 빠른 회의를 골라야한다.

따라서 입력되는 회의의 정보(시작시간, 종료시간)를 (종료시간, 시작시간)으로 저장한다면, 오름차순 정렬(sort함수)을 통해 한번에 정렬이 가능하다.

이렇게되면 종료시간은 빨리끝나는순으로, 시작시간은 빠른순으로, 같은 종료시간이 있는 회의는 그 중에 시작시간이 빠른순으로 정렬이된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
	int n;
	int count = 1;          // 사용할 수 있는 회의의 갯수
	cin >> n;			

	vector<pair<int, int>> times;		

	for (int i = 0;i < n;i++)
	{
		int start, end;
		cin >> start >> end;
        // (종료시간, 시작시간)으로 저장
		times.push_back(make_pair(end, start));
	}

	// 종료시간이 빠른순으로, 시작시간이 빠른순으로 정렬
	sort(times.begin(), times.end());

	// 종료시간이 제일빠른 회의선택
	int fTime = times[0].first;

	// 첫번째 회의를 제외하고
	for (int i = 1;i < n;i++)
	{
        // 종료시간 이후의 회의인 경우
		if (fTime <= times[i].second)
		{
			count++;
            // 다음 종료시간
			fTime = times[i].first;
		}
	}

	cout << count;
}