C++ 회의실배정 - 백준 알고리즘

1931번 회의실배정

---

문제

---

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

입력

---

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

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

출력

---

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

4

정답

---

// 13. Greddy Algorithms
// 회의실 배정
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

struct act{
	unsigned int start;		// 시작 시간
	unsigned int finish;	// 끝나는 시간
};

bool CompareWeigtht(const act& x, const act& y)	// 끝나는 시간으로 sort하기 위해 생성
{
	if (x.finish != y.finish)			// 끝나는 시간이 다를 경우 작은거에서 큰 순으로
		return x.finish < y.finish;
	else                                // 끝나는 시간이 같으면 시작 시간이 작은 걸로
		return x.start < y.start;
}

vector<act> v;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	act input;		// 입력을 받기 위해 struct act만큼 만듦
	int N = 0;		// 입력으로 받을 횟수
	cin >> N;

	for (int i = 0; i < N; i++)	// N만큼 반복하면서 input을 받고 받은 걸 vector<act> v에 저장
	{
		cin >> input.start >> input.finish;
		v.push_back(input);
	}

	sort(v.begin(), v.end(), CompareWeigtht);	// finish의 크기대로 sorting

	int k = 0;				// 끝나는 시간 위치
	int count = 1;			// 횟수 저장용도

	for (int i = 1; i < v.size(); i++)			// v의 size(=N) 만큼 반복
	{
		if (v[i].start >= v[k].finish)			// 끝나는 시간을 봤을 때 시작 시간이 같거나 더 늦으면
		{
			k = i;						// 끝나는 시간을 알기위해 k를 i의 값으로 받음
			count++;					// 횟수 추가
		}
	}

	cout << count << endl;			//횟수 출력

	return 0;
}

---